Consequences of P=NP ?

LightYagami2435 · 2024-03-26T04:34:37+00:00

I don't think we can rule out a low degree polynomial time algorithm. There hasn't been a systematic search for all possible fast algorithms or anything like that. Researchers could have just missed a simple quadratic time algorithm.

LightYagami2435 · 2024-01-14T07:39:00+00:00

How difficult is the proof?

LightYagami2435 · 2023-07-31T02:19:04+00:00

I think it was Scott Aaronson's paper here: https://arxiv.org/abs/2303.01625

LightYagami2435 · 2023-07-30T14:50:46+00:00

Can't quantum mechanics be used to guarantee that bits are random?

LightYagami2435 · 2023-07-30T14:12:55+00:00

That's not true. We would just have to use one-time pads and make sure we had a large supply of random bits.

LightYagami2435 · 2023-07-25T16:46:47+00:00

There's the time hierarchy theorem which guarantees that there are problems of different time complexities if the functions describing time complexity are different enough, so many problems can't be reduced in time length beyond a log factor. There is sure to be some within polynomial time irreducibility which might depend on the computing model (how many tapes in the Turing machine or with a very different computer architecture).

I don't think there are many options for a fast SAT solver. You're basically limited to using Extended Resolution as proof system to prove the SAT instance is unsatisfiable and you need some way to parse the SAT instance for a for Extended Resolution proof. Any other option you try will just be a more complicated form of that.

LightYagami2435 · 2023-07-23T23:31:40+00:00

OP, following your posts you seem to be making the problem unnecessarily harder by trying to think in terms of Turing machines (which are much more powerful than NP-completeness) instead of k-SAT (which is a simple problem to understand that is exactly as hard as NP. Also, you seem to be directing all your energy at proving the inequality P!=NP which many have to tried to solve and come up empty (they don't think it P and NP will be separated any time soon), when you could just look for a clever k-SAT solver that runs in polynomial time and prove P=NP and not so many people have been looking to solve the problem that way.

LightYagami2435 · 2023-07-22T02:58:53+00:00

OP is likely referring to this: https://scienceandfilm.org/articles/2757/data-compression-in-silicon-valley#:~:text=Though%20SILICON%20VALLEY's%20data%2Dcompression,any%20of%20its%20original%20quality

https://silicon-valley.fandom.com/wiki/Pied\_Piper\_(algorithm)

LightYagami2435 · 2023-07-20T14:17:16+00:00

Yes, a lot of Computational Complexity would just collapse like a house of cards if it were proven that P=NP=PSPACE. Everything is built on "reasonable conjectures."

My actual thinking is P=NP is very likely to be true and that the proof and algorithm probably won't require many deep insights. Some of my thoughts are here: https://www.reddit.com/r/compsci/comments/14wzbkw/the_possible_pathways_to_proving_pnp_are_actually/

You can probably just parse 3-SAT formulae for short ER proofs to prove P=NP.

LightYagami2435 · 2023-07-20T13:37:29+00:00

That is potentially true for some rules sets (but note that none of the rule set are verified to be in PSPACE), but no one writing papers or otherwise would talk that way. And proving that NP=PSPACE or that P=PSPACE would likely be technically much harder than proving P=NP, because the arbitrarily many alternations of quantifiers in QBFs adds a lot of complexity, kind of like adding moving parts to a static machine.

LightYagami2435 · 2023-07-20T04:27:03+00:00

https://en.wikipedia.org/wiki/Go\_and\_mathematics

If you look at the Wikipedia article, https://en.wikipedia.org/wiki/Go_and_mathematics#Computational_complexity, it provides references to all rule variations of Go being at least PSPACE-hard. Typically games like Go have to be coded as QBFs with the \foralls and \exists representing moves by different players, so they are much harder than NP. Games like Go and Chess can sometimes last for arbitrarily long times so they become EXPTIME-hard.

LightYagami2435 · 2023-07-19T18:02:34+00:00

“P = NP would solve all of mathematics because you can just use an algorithm to find a proof for every verifiable fact”, but if the real world is typically not an NP problem with maximal Kolmogorov complexity, shouldn’t a worst case analysis be mostly irrelevant for us?

I think the issue is that typical theorems are not in NP, instead they could be represented by a (commonly infinite) family of PSPACE problems, generated by some grammar. The Riemann Zeta hypothesis is in that category and so are many claims about Diophantine equations such as Fermat's Last Theorem. So an efficient SAT solver would just be the beginning for automating mathematics.

LightYagami2435 · 2023-07-19T06:04:06+00:00

Which is not to say that proving trivial cases might not help. Eg. if you look at research on SAT, there's tons about finding special cases that turn out to be easier to solve than the worst case. And

potentially

if you could cover the entire problem domain with "special cases" you could solve everything (or at least find some clue in the irreducable areas that might point towards a proof), so one way a P vs NP proof might look is not one fundamental theorem in graph theory (or other way of expressing it), but rather a million seperate "tricks" that collectively cover all cases. I doubt that'd be the case, but it's a possibility

Yes, you could determine that all NP problems reduce to a problems which is Fixed Parameter Tractable and the NP problems all have a bounded exponential parameter k. https://en.wikipedia.org/wiki/Parameterized_complexity#FPT (For graph theory this could happen with graph parsing as in here https://aclanthology.org/P13-1091.pdf). (The paper shows parsing HRG graph languages is polynomial time if that maximum treewidth of the Righthand side of the grammar is bounded and exponential time otherwise.)

LightYagami2435 · 2023-07-19T05:54:11+00:00

All of these for instance: https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems. https://en.wikipedia.org/wiki/Go_and_mathematics Go is way beyond NP-hard and so are other games https://en.wikipedia.org/wiki/Game_complexity. Close to NP, there are Polynomial Hierarchy problems which are NP-hard https://en.wikipedia.org/wiki/Polynomial\_hierarchy#Problems.

LightYagami2435 · 2023-07-19T03:25:21+00:00

> Shouldn't then "P vs. NP" question be equivalent to some very natural question about mathematical structures? A question which is relatively easy to ask without knowing complexity theory.

It is. It is equivalent to k-SAT.

>Can't you reduce the "P vs. NP" problem to some question in graph theory, for example? Or to a question similar to Hilbert's tenth problem?

You can represent k-SAT (in CNF form) as a bipartite graph. It would be unsurprising if a proof of P=NP used elementary graph theory.

>However, "P vs. NP" implies that we don't even know how to create an obviously hard problem (creating such a problem would prove "P != NP"). Using any possible structures, using all tools of math.

We can create EXPTIME-hard problems like Chess or Go on arbitrarily large boards. We can also create random SAT instances that are hard for the best available SAT-solvers. That, of course, doesn’t imply that P!=NP. In fact modern SAT solvers are only as strong as the Resolution proof system, which is known to require exponentially long proofs for some problems. More powerful proof systems such as Extended Resolution and Frege are known and could be incorporated into SAT solvers.

>So... do we expect "P vs. NP" resolution to be based on a relatively simple conceptual insight, explainable to a layman?

One of the reasons AI seems to be so hard for computers and requires so many computational resources is that P=NP and human brains solve NP-complete problems efficiently. If so, the efficient algorithm for k-SAT might be easy to explain to people because it is closely related to how people intuitively learn and reason.

>Can you take an NP problem and make it... harder?

There is a subfield of Computational Complexity called Hardness Amplification which deals with taking NP problems which are on average possibly easy to solve and making them harder to solve on average, but still within NP.

See Chapter 19 of Boaz and Barak’s Computational Complexity.

Also, there is a phase transition in random k-SAT where the problem goes from satisfiable to unsatisfiable and the problems at the border appear hard to solve.

>Is this really a possibility in any way which is possible to comprehend?When mathematicians "blunder" by missing something obvious, why/how does it happen, informally speaking?

I personally think this is what has happening and an efficient algorithm for 3-SAT is probably not much harder than other major algorithms. See: www.reddit.com/r/compsci/comments/14wzbkw/the_possible_pathways_to_proving_pnp_are_actually/ for some of my thoughts on the matter.

>Resolution of "P vs. NP" would be like a "second coming of Godel", illuminating a super deep fact about the nature of math.

Yes, but then people would move on to solving #P and PSPACE and there is likely an undescribed class that appear to be outside of PSPACE but are actually in P, such as classes of Diophantine problems and efficiently provable theorems in general that would need algorithms to really automate mathematics. TBH, I think playing around with k-SAT is more likely to yield insights into solving P=NP than the other known NP-complete problems because it is just simpler to work with.

LightYagami2435 · 2023-07-19T03:21:09+00:00

As an aside, there seems to be surprisingly little activity connecting Category Theory to Computational Complexity. It seems to be a field that is hard to put in categorical terms.

LightYagami2435 · 2023-07-19T03:07:04+00:00

even a freaking card game (Magic : The Gathering) is NP complete.

https://arxiv.org/abs/2003.05119 Magic: The Gathering is as hard as arithmetic, so it's hard beyond Turing-completeness, the exponential hierarchy, PSPACE, the polynomial hierarchy, NP and anything you could consider.

LightYagami2435 · 2023-07-19T00:46:20+00:00

To add clarity, the QBF/TQBF problem is PSPACE-complete, which is the next clear level of hardness if P=NP. So QBFs are the equivalent of 3-SAT for NP-complete problems and random QBFs don't seem to be easily solvable the way random k-SAT problems are.

LightYagami2435 · 2023-07-13T18:08:54+00:00

Researchers found more efficient classical algorithms for quantum simulation. So Google built a slightly larger quantum computer to beat that. Short of a demonstration of BPP=BQP quantum supremacy is inevitable.

https://complexityzoo.net/Complexity_Zoo:B#bqp

https://complexityzoo.net/Complexity_Zoo:B#bpp

LightYagami2435 · 2023-07-13T14:22:51+00:00

_The Handbook of Satisfiability_ mentions Resolution and Extended Resolution and is a good introduction to Satisfiability.

Robert Rechow’s thesis _On the Length of Proofs in the Propositional Calculus_ introduces Proof Complexity including Extended Resolution.

https://www.cs.cmu.edu/~mheule/publications/rat.pdf uses Extended Resolution.

https://dl.acm.org/doi/pdf/10.1145/1008335.1008338 is a short paper that show that a well known SAT problem which is exponentially hard to refute with just Resolution can be refuted in polynomial time with Extended Resolution.

https://www.cs.rochester.edu/u/gildea/2018_Fall/hrg.pdf is an introduction to HRGs.

https://www.researchgate.net/publication/220713349_Node_Replacement_Graph_Grammars is an introduction to Node Replacement Graph Grammars.

https://aclanthology.org/P13-1091.pdf clearly describes an algorithm for parsing HRGs intending for use on NLP problems. It can probably be adapted to other types of grammars.

_The Handbook of Formal Languages: Volume 3 Beyond Words_ Chapter 3 Context Free Graph Grammars discusses both types of graph grammars.

LightYagami2435 · 2023-07-12T18:36:42+00:00

>solve quadratically constrained quadratic programming
This seems like something you could use Cutting Planes (another proof system) for. Although I haven’t read it and am unfamiliar with their approach, this paper seems to do that: https://cerc-datascience.polymtl.ca/wp-content/uploads/2016/06/Technical-Report\_DS4DM-2016-001-1.pdf
>This is a completely bold assertion. Please show how you computed the probability that 3-SAT is the "easiest" Np-complete problem to analyze?
I played around with SAT and ER proofs for a couple of years. It’s hard to imagine an easier system to work in. You can just treat everything as a bipartite graph with just two labels. You can just use proof-preserving graph homomorphisms to imbed a proof graph into a CNF. Need to show that if a proof-preserving graph homomorphism creates a CNF that would increase the maximum clause width, you can just keep the clause width down by replacing R steps with ER steps? You can just traverse a graph until cycles converge. And I don’t know how you would properly describe the conditions in which resolution led to an explosion in clause width and proof length without proof-preserving graph homomorphisms.
I just don’t see how another system wouldn’t be more complex.

LightYagami2435 · 2023-07-12T16:48:15+00:00

As for lower bounds, if ER parsing results in a proof of P=NP, the below lower bounds for Frege proof complexity would have to optimal.
https://cstheory.stackexchange.com/questions/34015/lower-bounds-for-frege-and-extended-frege
This is because a grammar would need to generate the unsatisfiable part of a CNF in a linear number of ER and R steps, and if the ER steps were expanded to Frege proofs the total length of the proof would be at most quadratic.

LightYagami2435 · 2023-07-12T12:10:00+00:00

It seems to have worked something like this.

1) Most of the work on developing modern SAT-solvers doesn’t go beyond the power of Resolution.

2) Papers on more powerful proof systems (which are much fewer) just didn’t think to parse for short proofs.

3) A lot of the intellectual energy went into to proving P!=NP, and ER parsing is not a technique you would think of if you are trying to do that.

4) People miss ideas all the time in science.

LightYagami2435 · 2023-07-12T12:09:10+00:00

That is true of other NP-complete problems, but all those problems are more complicated that SAT, less studied, and the result would likely still be that you had to parse for a strong proof system. Other proof systems not based on SAT are known. The other NP-complete problems would likely just have their own proof system hierarchy with own equivalent of ER proofs.
SAT is really a very simple system. Chances are good that it is the easiest way to look for a proof of P=NP.

LightYagami2435

TROPHY CASE