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. 
 •  0 comments  •  flag
Share on Twitter
Published on April 04, 2021 21:30
No comments have been added yet.


Lance Fortnow's Blog

Lance Fortnow
Lance Fortnow isn't a Goodreads Author (yet), but they do have a blog, so here are some recent posts imported from their feed.
Follow Lance Fortnow's blog with rss.