Boris Bukh asks a rather novel question about the complexity of Max 3SAT. Given a 3CNF formula , we know it is NP-hard to approximate the maximum number of clauses that can be simultaneously satisfied. But how many bits of information can we efficiently compute about Put another way, how many possible values of can we efficiently rule out? If the formula has clauses, then we know that the possible value of is one of possible values, but it is difficult to see how this can be narrowed down much more. On the other hand, there is an argument that you cannot narrow the set of possible values down to a constant, or even a constant times , unless the polynomial hierarchy collapses. But there is still a big gap.
John Sidles asks a series of questions that are nominally related to but that can also be phrased about the proof that, say, every problem in has a uniform family of polynomial size circuits.
In the latter setting, we start by showing that from a Turing machine , a time bound , and a size bound , we can construct a circuit of size polynomial in , , and the size of , such that on every input of length the circuit simulates what the Turing machine does on input for steps. If a language is in , then there is a Turing machine and a polynomial bound such that decides on every input of length in time at most ; given , we can then construct a circuit that solves on inputs of length by applying the circuit simulation with .
But, the question is, what if we do not know ? This might sound like a rather strange issue, like someone objecting to the commutative property of addition by saying, how I am going to use if I do not know and ?
There is, however, a real issue, and one that often confuses students, which is the “non-constructive” nature of the definition of complexity classes. That is, a language belongs to if there exists an algorithm and there exists a polynomial time bound such that the algorithm is correct and always terminates within the time bound. The definition does not require that we know the algorithm and the time bound. It might seem that of course it does not, because “we” and “know” are not mathematical concepts, but consider the following example.
Let be the language of integers such that there is a pair of twin primes larger than . Is this problem in ? Of course! What is the algorithm? Well, I don’t know, although I can exhibit an infinite list of possible algorithm, and prove that all of them work in linear time and that at least one of them is correct. Less artificially, the Robertson-Seymour theory gives polynomial time algorithms for graph properties that are closed under minors, but to construct an algorithm for such a property one needs to know the finite set of obstruction, and there is no general way to find such a set, even in principle.
If is meant to model problems that can be efficiently solved, does it make sense for the definition to allow problems such as the ones above that we do not, in fact, know how to solve efficiently?
An alternative would be to work with “constructive ”, let’s call it , that is, the class of languages that have polynomial time algorithms such that the correctness and time-boundedness of the algorithm are provable, say, in ZFC. Now if someone tells us that a given problem is in we can, at least in principle, find the algorithm and time bound. Constructive definitions could be given for all complexity classes.
Why don’t we work with the constructive definitions? I think that one problem is that they introduce ugliness, unnecessary dependencies on certain choices (why ZFC and not ZF, or what about large cardinal axioms?), to address one of the most benign ways in which the formal definitions of complexity classes deviate from their intuitive meaning.
But more importantly, while a constructive inclusion is a more satisfactory statement than the non-constructive analog, there is something unsettling about a separation from a constructive class. Suppose, for example, that there is a proof that SAT is not in . Such a proof would still leave open the possibility that SAT allows a fast algorithm, it’s just that the correctness and efficiency of the algorithm cannot be proved. But it could even be that we discover such an algorithm, verify that it works well in practice, and reap all the practical benefits of , so in this case the constructive definition does not capture what is going in “practice.”
One could then say that the “right” way of proving is to show that for every correct algorithm for SAT we can prove an explicit superpolynomial time lower bound. Or should it be, for every polynomial time algorithm we can explicitly find infinitely many inputs on which the program is wrong? Should this be required of all algorithms or all the ones for which correctness or time bound are themselves provable?
Very quickly, we fall into the mathematical rabbit hole of intuitionistic logic, in which the negation of the negation of a statement is not the same thing as statement .