Now this is my home question. It boils down to the satisfiability problem. Someone suggests the bound is exponential, but with a very small exponent. I think this is a good answer for the observation that SAT is fast for small instances. But we want it to be better, i.e., polynomial. But the boundary between polynomial and exponential is very murky.
Thinking without search. Searching = thinking.
Without a search tree, you can’t prove that something doesn’t work.
Is there a short proof that something doesn’t work? Is there a general strategy to find such proofs?
That amounts to a proof that P ≠ NP.
But it needs to be worked out.
Is there magic, besides logic?
Or if you can prune the search tree sufficiently often.
In general, a search tree can’t be pruned.
Are the pruning patterns finite or infinite?
My guess is that there are infinitely many.
Pruning!
In general, search is inevitable.
Derive a contradiction. Look at SAT instances.
Define search. Searching is the process of looking at each variable in turn. But the tree can be big or small.
A proof is a search tree.
There are no short proofs. But this needs verification.
What do you mean by short proofs?
Are there logic and magic? Accidentally…. What does that mean?
Is there a short proof for UNSAT? A proof much shorter than the search tree.
I’m asking if NP = coNP.
Thinking without search is possible. Just convert the formula to DNF.
But that is searching.
Search, exhaustive search, is unavoidable.
Are they the only two strategies?
What is thinking? It’s analyzing the formula.
If this pattern occurs exponential number of times, then it’s already exponent. If, otherwise, it only appears polynomial number of times, then the saving is polynomial. In other words, learning cannot make an exponentially large search space polynomially small.
I’m assuming the running time of discovering a pattern is polynomial. If not, after discovering the pattern, you are already spending too much time, exponential time.
Sophisticated
How do you define a clever method?
I thought this was impossible.
Failure with this is not failure. Failure not to do this
Given a formula and a solution, find the minimum cardinality of a subset which is also a solution. For example, the formula is \(x_1\lor x_2\) and the solution is setting both variables to true. Now a subset is just setting \(x_1\) to true. I think this problem is no easier than SAT itself.
但很重要
I don’t care. I just want to do P vs NP.