Do any NP-reductions use deep mathematics? Non-rhetically
BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP.then what direction would we think Factoring in P or NPC?
STUDENT: In P. After all, Number Theory is a deep subject and I can imagine some deep Theorem in it leading to FACTORING in P.
BILL: That cuts both ways. I can imagine some deep theorem in NT being the key to showing
FACTORING poly-reduces to SAT
STUDENT: Deep mathematics HAS been used for algorithms. Factoring algs is one example, The graph minor theorem yielding MANY problems in P is another. Can you give me an example where deep mathematics has been used for an NPC reduction?
BILL: Oh. Gee. I do not know of any.
STUDENT: If only you had some mechanism to ask the theory community. Maybe you could call it a web log, or weblog.
BILL: If only...
QUESTIONS1) Are there any NPC reductions that use deep math? (I realize that the phrase `deep math' is not well defined,)
2) Are there other reductions that use deep math?
3) If P NE NP then: For all epsilon there is no approx-alg for MAX3SAT which yields \ge (7/8 + epsilon)OPT
For all delta there is no approx-alg for CLIQ which yields > n^{-delta} OPT
No approx-alg for SET COVER which yields \ge (ln n + o(1))OPT.
All of these proofs use the PCP machinery or something similar. My impression is that the original PCP theorem, while long, hard, and impressive, did not use deep math. I have a vague memory of some paper or PhD thesis stating that the ONLY theorem needed was that a poly of degree d over a finite field has \le d roots.
However to get the optimal lower bounds seemed to use some deep math. But I am more ASKING than telling.
STUDENT: In P. After all, Number Theory is a deep subject and I can imagine some deep Theorem in it leading to FACTORING in P.
BILL: That cuts both ways. I can imagine some deep theorem in NT being the key to showing
FACTORING poly-reduces to SAT
STUDENT: Deep mathematics HAS been used for algorithms. Factoring algs is one example, The graph minor theorem yielding MANY problems in P is another. Can you give me an example where deep mathematics has been used for an NPC reduction?
BILL: Oh. Gee. I do not know of any.
STUDENT: If only you had some mechanism to ask the theory community. Maybe you could call it a web log, or weblog.
BILL: If only...
QUESTIONS1) Are there any NPC reductions that use deep math? (I realize that the phrase `deep math' is not well defined,)
2) Are there other reductions that use deep math?
3) If P NE NP then: For all epsilon there is no approx-alg for MAX3SAT which yields \ge (7/8 + epsilon)OPT
For all delta there is no approx-alg for CLIQ which yields > n^{-delta} OPT
No approx-alg for SET COVER which yields \ge (ln n + o(1))OPT.
All of these proofs use the PCP machinery or something similar. My impression is that the original PCP theorem, while long, hard, and impressive, did not use deep math. I have a vague memory of some paper or PhD thesis stating that the ONLY theorem needed was that a poly of degree d over a finite field has \le d roots.
However to get the optimal lower bounds seemed to use some deep math. But I am more ASKING than telling.
Published on April 04, 2021 21:30
No comments have been added yet.
Lance Fortnow's Blog
- Lance Fortnow's profile
- 4 followers
Lance Fortnow isn't a Goodreads Author
(yet),
but they
do have a blog,
so here are some recent posts imported from
their feed.
