Here is a link to recordings of invited and tutorial talks at the recent STACS 2015 conference. (Slides are available here.) These recordings include my tutorial talk on algorithmic game theory, all 3 hours of it, which may possibly be of use to writers of articles with titles like The Top Ten Mistakes you make When Giving a Technical Talk.
Possibly the commonest mistake (other than dressing badly) is to assume too much knowledge on the part of the audience. This mistake wastes the opportunity for a “big win” in which you present some fact or result that most people in the room don’t already know, but which should by rights be ingrained in their DNA. I got to do that via presenting Megiddo’s 1988 result that NP total search problems cannot be NP-complete unless NP=co-NP. To be clear, an NP total search problem is one where every instance has an easy-to-check solution, for example FACTORING, where the output is a prime factorization of an input number, or NASH, where the output is a Nash equilibrium of a given bimatrix game. This is the reason why we don’t bother to look for an NP-hardness result for NASH, and have to use an obscure-looking complexity class like PPAD.
It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm A that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING. Now consider what happens when pass a non-satisfiable formula Φ to A. What you end up concluding is that any run of A must constitute a (short) certificate that Φ is not satisfiable, implying NP=co-NP. A will process Φ, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.
Possibly the commonest mistake (other than dressing badly) is to assume too much knowledge on the part of the audience. This mistake wastes the opportunity for a “big win” in which you present some fact or result that most people in the room don’t already know, but which should by rights be ingrained in their DNA. I got to do that via presenting Megiddo’s 1988 result that NP total search problems cannot be NP-complete unless NP=co-NP. To be clear, an NP total search problem is one where every instance has an easy-to-check solution, for example FACTORING, where the output is a prime factorization of an input number, or NASH, where the output is a Nash equilibrium of a given bimatrix game. This is the reason why we don’t bother to look for an NP-hardness result for NASH, and have to use an obscure-looking complexity class like PPAD.
It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm A that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING. Now consider what happens when pass a non-satisfiable formula Φ to A. What you end up concluding is that any run of A must constitute a (short) certificate that Φ is not satisfiable, implying NP=co-NP. A will process Φ, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.
4 comments:
Dear Prof Goldberg,
Your post was eye-catching.
It turns out that all the used to be NP-complete problems are NP-complete iff (NOT) NP-complete.
Just by addressing the question:
"Is Paradox Recognition decidable?"
Theorem: P=NP iff P!=NP.
SAT is NP-complete iff SAT is (NOT) NP-complete
The Kleene-Rosser paradox is a counter-example to NP-completeness.
================================================
Russell's Paradox: The set that contains all the sets that do not contain themselves. If you ask the question:"Does it contain itself?". The answer would be it contains itself iff it does not contain itself.
The Kleene-Rosser Paradox: Roughly, the function that may not be applied to itself, when combined with itself, it negates itself.
This function is a lambda expression as "k:= NOT (x x)" which reads: The meaning of k is: "x" may not be applied to "x". Then deriving "kk" results in the paradox:
kk= NOT kk
If you assume that this function is total, you derive a contradiction, then it is not total. Then, if you assume that it is not total, again, a contradiction is derived, then it is total. So, it is total iff it is not total. The Church-Rosser argument shows that this function is undefined. Here,
https://www.academia.edu/7160422/Mathematics_is_Inconsistent
it has been shown as defined iff it is undefined and decidable iff it is undecidable, both on the lambda-calculus and Turing machines. Below is a proof sketch.
================================================
Step 1. Cook_Levin: For all w in L in NP,
M accepts w iff \exists A(w)=SAT.
Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
M_KR accepts w_KR iff e^-1(w_KR)= NOT e^-1(w_KR).
Step 3. Put M=M_KR and w=w_KR.
==> L.H.S. of (1) = L.H.S. of (2).
==> R.H.S. of (1) = R.H.S. of (2).
==> There is no SAT(w_KR).
==> SAT is (NOT) NP-complete.
==> SAT is NP-complete <==> SAT is (NOT) NP-complete,
Cook's proof is still correct despite the contradiction.
==> P=NP iff P!=NP.
================================================
best,
Rafee Kamouna.
Pedantically, isn't the appropriate term NP-hard rather than NP-complete? For a problem to be NP-complete, it must be in NP, and a search problem cannot be, since it is not a decision problem.
Answer to comment 2: a partial search problem, e.g. "find a satisfying assignment to a given boolean formula" can be (and is) NP-complete. (The word "partial" refers to the fact that some but not all formulae have solutions, i.e the unsatisfiable ones don't have solutions. Same usage as "partial function".
NASH and FACTORING are NP total search problems (any instances have easy-to-check solutions). They are not to be confused with total search problems not in NP, like the search for a winning move in chess (to be safe, I should say something like, identify a player who can guarantee not to lose, and a move that retains that guarantee after he makes it). There's no obvious way to check that such a move has the claimed property.
I think the title of the post is technically correct (subject to complexity theoretic assumptions etc), and if you want to replace NP-complete with NP-hard, you would also have to say "NP total search problem" rather than just "total search problem".
What about paradox recognition?
The banned question in all TCS conferences/journals.
best,
Rafee Kamouna.
Post a Comment