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...
QUESTIONS
1) 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.
Laci’s proof that graph isomorphism is polylog relies on the classification of finite simple groups. You almost certainly don’t need the whole classification, but my understanding is that you need the parts that cover the groups in question.
ReplyDeleteI think your dismissal of the PCP Theorem is overly hasty. Significant creativity and original thought went into going from the Schwartz-Zippel Lemma to verifying computations using the sum-check protocol. If you want to classify that as “not deep” that’s one thing, but the deepest part of the (original) PCP theorem is the invention of the VC paradigm in the 90s.
I was not dismissing. I was more asking IF it used deep math. If it doe not that would NOT take away from how awesome it was- I did say that.
DeleteFourier theory was introduced to CS with Håstad's optimal inapproximability results. Today it might not be considered deep, but I recall when it still was.
ReplyDeleteAlso there are Algebraic Geometry codes which use downright arcane mathematics...
The definition of AI problems are AI problems that haven't been worked out yet. Then they are just algorithms.
DeletePossibly problems from computational topology or computational geometry qualify? I cannot judge the mathematical depth of the following result (my knowledge about 3-manifolds is very limited), but the little I understand impresses me: "3-manifold knot genus is NP-complete" by Agol, Hass and Thurston https://doi.org/10.1145/509907.510016
ReplyDeleteAH, the 3-manifold ... problem certainly uses deep math by any definition.
DeleteI wonder how common such problems are- perhaps more common in Comp Top or Comp Geom then in other parts of CS.
Are there deep math reductions in Arithmetic versions of the P/NP classes? I'd bet they would need deeper facts about varieties and what not.
ReplyDeleteWhat about Mulmuley's work? Seems to require some deep math.
From the commments it seems that concrete models and PCP DO use some deep math.
ReplyDeleteHow about my original question- do any NP reductions use deep math?
I think you need to say a little more about what you mean by "deep." Does it just mean "unfamiliar"? Or "from an area of mathematics with a glamorous reputation"? If we are trying to make an educated guess about whether a conjecture is true or false, then personal familiarity and glamor presumably are not very relevant concepts.
ReplyDeleteAnother thing I don't understand is why you haven't answered your own question; if PCP uses deep math then the proof of NP-hardness of certain inapproximability results must use deep math, right?
The following MathOverflow question contains some interesting opinions about the word "deep":
https://mathoverflow.net/q/139607/
The PCP stuff shows problems are hard to APPROXIMATE.
ReplyDeleteBy `reductions' I meant proofs that SETS are NP-hard.
So do any of those use `deep math'
What is `deep math'? A good question which many of the comments have also commented on and helped me realize more what I was trying to ask. I will now phrase several better-defined questions
a) Are there any proofs that a SET is NPC that uses math that a good
Senior CS major (who is not also a math major) has not seen and would
take to much time in a course to explain.
b) Replace `good senior CS major (who is not a math major)
with
good senior CS major who IS a math major
1st year grad student in CS (who was/was not also a math major)
While not likely to be NP-complete, Tensor Isomorphism-complete problems definitely use a lot of deep math. https://arxiv.org/abs/1907.00309
ReplyDelete"Deepness" is subjective. Suppose by "deep math" you mean that a student in a graduate level algorithms course will have trouble understanding it (which seems to be the case in your comment above). Then this is just poor classification due to exposure to different areas.
ReplyDeleteIf your problem is easy to describe typically the reductions "look" easy just because they can be understood by many people, even if they take a lot of ingenuity to come up with.
If your problem requires several graduate math courses' worth of background to even describe then of course the reduction "looks" difficult �� even if the reduction ends up being trivial and straightforward.
I still don't understand your attempted distinction between APPROXIMATE and SET. By "SET" you just mean a decision problem, right? But as you know, there is a standard way to extract an NP-complete decision problem from one of the PCP-type NP-hard approximation problems.
ReplyDeleteIn any case, the 3-manifold knot genus problem mentioned by Hermann Gruber would seem to qualify according to your most recent definition, for the (trivial?) reason that it would take too much time in the course to even explain what the SET is in the first place.
I imagine that the proof that MCSP is NP-hard uses "deep math".
ReplyDeleteYES the 3-manifold problem definitly qualifies.
ReplyDeleteYou may know something I do not and would be curious to know.
Here is what I know (and everyone does)
CLIQ = {(G,k) : G has a clique of size k} is an NPC set
proof is NOT deep math
FCLIQ(G) = return the size of the max cliq
FLIQ in FP iff CLIQ in P hence we do not think FLIQ is in P.
(Same for returning an actual clique)
You say that from the PCP results saying FCLIQ is hard to
approximate you can extract a DECISION PROBLEM that is NP-complete.
If you mean a GAP problem (given a graph G that you are PROMISED
has a large or small clique, det which one) then yes.
If you mean an actual decision problem then I do not know that and
would be enlightened if you post on it- or if its too long or something then email me.
I had in mind the gap/promise problem. I see now the distinction you are trying to draw.
DeleteA good amount of number theory is used in the NP-completeness proof of Diophantine binary quadratic equations:
ReplyDeleteax^2 + by - c = 0
(Manders and Adleman, 1977)