Skip to content

Consistency and P=NP

May 11, 2020


Can we at least show that {P\neq NP} is consistent?

[ From personal page ]

Jan Krajicek is an expert on linking computational complexity and mathematical logic. He has authored four books on this area including the often cited text Bounded Arithmetic and Complexity Theory. Moreover, he has studied the consistency of various of theories and whether they can prove {\mathsf{P \neq NP}} and related questions.

Today I thought we would discuss consistency proofs in general.

Lately I have been thinking about {\mathsf{P=NP}} and logic, with emphasis on consistency results. Thanks to Kurt Gödel’s famous Second Incompleteness Theorem we know that consistency theorems are difficult to prove. In particular he showed that

Theorem 1 (Informally) Any sufficiently powerful consistent theory cannot prove that it is consistent.

In order to prove that some theory {T} is consistent we need a stronger theory say {T^{*}}. But to prove this theory is itself consistent we need an even stronger theory {T^{**}} and so on. As they say:

Its turtles all the way down.

It is not clear who first said this, but an 1854 transcript of debates between a mainline and maverick minister records the former (Joseph Berg) saying of the latter (Joseph Barker):

My opponent’s reasoning reminds me of the heathen, who, being asked on what the world stood, replied, “On a tortoise.” But on what does the tortoise stand? “On another tortoise.” With Mr. Barker, too, there are tortoises all the way down.

Recall a logical theory is consistent provided it never proves {A} and {\neg A} where as usual {\neg A} means “not” {A}. Thus a theory is consistent provided it will never prove both {A} and {\neg A}. This means that once a statement is proved we are done. There will be no surprise in the future.

Bluntly: I would hate if my paper showing that {X} is true, was followed by your paper showing that {X} is also false. Besides pride I would hate this because, then any statement is true. This would certainly reduce any interest in my theorem proving {X} and also in your theorem proving {\neg X}. This is “ex contradictione quodlibet”.

The rule

\displaystyle  X \text{ and } \neg X \implies \text{``Pigs can fly''}

must be true. Right. Or must it? In a moment, but first some examples of consistency issues.

Failure of Consistency

Since David Hilbert explicitly, and before implicitly, there has been interest in showing that our math theories are consistent. It may seem strange that consistency could ever be an issue, but read on.

{\bullet } A theory that was thought to be inconsistent:
The creation of non-Euclidean geometries asked could these geometries be consistent? The answer is yes. It is possible to show that they are as consistent as Euclidean geometries. This done by building models of their new geometry by using Eucildean geometries in clever ways.

{\bullet } A theory that was thought to be consistent:
The famous Russell paradox destroyed early formulations of set theory. Bertrand Russell noted that the formulations allowed defining the following as a set:

\displaystyle  S = \{ x \mid x \not\in x \}.

But this is a problem, since it creates logical statements that are equivalent to their negations:

\displaystyle  x \in S \iff x \not\in S.

Fixing this led to the creation of modern set theory ZF. It is named Zermelo-Fraenkel set theory, after Ernst Zermelo and Abraham Fraenkel.

{\bullet } A theory that was thought to be—still unclear:
Willard Quine’s theory “New Foundations” (NF) of set theory remains a problem. There are some possible relative proofs that show that it is as consistent as normal set theory. See this for the claim by Randall Holmes that NF is as consistent as ZF—see this.

Length-based Immunity

The sentences used by Krajicek and his co-authors Jan Bydzovsky and Igor Oliveira in a recent paper deal with forms of length-based immunity. The complexity-theoretic definition is this:

Definition 2 A language {B} is length-based immune (LBI) to {\mathsf{P}} if for every polynomial-time program {P_i}, there are only finitely many {n} such that {P_i} is correct on strings of length {n}. That is,

\displaystyle  (\forall P_i)(\exists \ell)(\forall n > \ell)(\exists x \in \Sigma^n): P_i(x) \neq B(x).

This property is akin to immunity: not having an infinite easy subset. The known {\mathsf{NP}}-complete sets are not immune: for instance there are many easy cases of SAT. Under the Isomorphism Conjecture, no {\mathsf{NP}}-complete set is immune. Whether SAT can be length-based immune might depend on details of how formulas are encoded, but under a “natural” encoding one might expect length-based immunity to hold.

Of course, if {\mathsf{NP}} has a length-based immune set then {\mathsf{P \neq NP}}. Say a theory {T} is “adequate” if it is consistent and proves basic facts about complexity classes such as that one. Then for an adequate theory {T}:

Suppose we prove it is consistent with {T} that {\mathsf{NP}} has an LBI set. Then {T} cannot prove that {\mathsf{NP}} does not have an LBI set. Since {\mathsf{P = NP}} imples that {\mathsf{NP}} does not have an LBI set, this yields the simple and notable conclusion that {T} cannot prove {\mathsf{P = NP}.} That is, {\mathsf{P \neq NP}} is consistent with {T.}

Krajicek, as we said before, has tried to prove that complexity statements like {\mathsf{P \neq NP}} are consistent. The trouble is that such questions are difficult. So he and others have worked on showing that these questions are at least consistent with theories {T} of arithmetic. It seems too hard to handle Peano arithmetic yet, so they work with theories {T} that are weaker than Peano arithmetic—but still adequate. For these theories, Krajicek and company have results for some variations of Definition~2, albeit ones that seem not to have a direct relation to {\mathsf{P = NP}}. The two main ways to vary the Definition~2 are:

  • Change the class {\mathcal{C}} that has—or may not have—a length-based immune set to something else, for instance {\mathcal{C} = \mathsf{P^{NP}}}.

  • Change the class {\mathcal{Q}} of programs the sets are immune to from polynomial-time programs to something else.

Fixed Polynomial Size Circuits

They fix a constant exponent {k} and take {\mathcal{Q}} to be families of circuits {C_n} of fixed polynomial size {n^k}. The circuits can be non-uniform, and indeed the unprovable statements are defined by a process that is not constructive.

Circuits of linear or other fixed polynomial size are a fascinating and important topic in themselves. We have posted about Ravi Kannan’s famous theorem that for every fixed {k}, the second level of the polynomial hierarchy has languages without {n^k}-sized circuits. The upper bound has since been pushed lower but not all the way to {\mathsf{P^{NP}}}. It is of course believed that {\mathsf{NP}} has languages without {n^k}-sized circuits, since SAT is believed to require super-polynomial size. But the question of whether {\mathsf{NP}} has sets that lack such circuits—let alone being immune—is currently not known to have implications about {\mathsf{P = NP}}.

Note that the easy instances of SAT that we alluded to above are easy for linear-size circuits. Moreover, whether {\mathsf{P}} itself has—or doesn’t have—sets that are length-based immune to {n^k}-size circuits is a statement that can be plausibly argued either way. Krajicek and Oliveira had earlier proved that a particular theory called PV—which we will discuss next—cannot prove for any {k} that every language in {\mathsf{P}} has {n^k}-sized circuits. This unprovable statement, without the LBI condition, strikes us as less plausible—hence less surprising that a weaker theory like PV cannot prove it. What they prove now is:

Theorem 3 For any fixed {k}, PV cannot prove that every language in {\mathsf{P}} allows circuits of size {n^k} to get the right answers on infinitely many input lengths. That is, it is consistent with PV that {\mathsf{P}} has sets that are LBI to {n^k}-size circuits.

Moreover, for some particular theories called {S^1_2} and {T^1_2} that extend PV, it is consistent that {\mathsf{NP}}, respectively {\mathsf{p^{NP}}} has sets that are LBI to {n^k}-sized circuits.

We will talk a little more about these theories.

PV and Related Theories

What are the candidate theories for {T}? One is PV, a theory created by Steve Cook. For every polynomial-time program {P_i}, PV has a symbol {\varphi_i} for the function that {P_i} computes. Then add all the equations that these functions satisfy and you have PV. For example,

\displaystyle  2^{x+1} = 2 \times 2^{x},

for the exponential function {x \rightarrow 2^{x}}.

PV can formalize and prove properties of program-building constructs like composition and bounded for-loops that preserve running in polynomial time. It can formalize the concept of polynomial-size Boolean circuits and establish basic facts about them. It can prove deep results like the PCP theorem and more.

Thus showing that your favorite statement is at least consistent with PV would be neat. It is critical that PV only allows equations as axioms. Thus PV does not axiomatize the statement

\displaystyle  \forall x \exists y>x \ 2^{y}-1 \text{ is a prime}

even if it is true. The more-formal statement of their theorem for PV is:

Theorem 4 For every {k}, there is a formula {\varphi(x)} in the language of PV such that the statement

\displaystyle  \Upsilon_{\varphi} = (\forall \ell)(\exists n > \ell)(\exists C_n \text{ of size } \leq n^k)(\forall x\in \Sigma^n): \varphi(x) = C_n(x)

is not provable in PV, and such that the function {\varphi(x)} is polynomial-time computable.

The theorem is not diminished if we restrict attention to yes/no formulas and circuit outputs. Thus it is not provable that every language in {\mathsf{P}} has infinitely many input lengths at which it is easy for {n^k}-sized circuits. Put another way, it is consistent with PV to assert (for any {k}) that {\mathsf{P}} has a language that lacks size-{n^k} circuits {C_n} in the strong sense of every {C_n} making an error on some string of length {n}, beyond a finite number of {n}. This is stronger than saying the language lacks {n^k}-size circuits, which makes the consistency more notable.

Where PV lacks power is with the unrestricted induction enjoyed by Peano Arithmetic. The other theories {S_2^1} and {T_2^1}, which were named and studied by Sam Buss in the 1980s, add more induction—by limiting the kind of formulas on which it is allowed.

Here is where we point to the papers for details. The devil in those details is that the exceptional formulas {\varphi} are not expressly constructed. For one, the proofs of their theorems use a disjunction about whether the polynomial hierarchy collapses at a certain level. Note that something similar is already at work in our post on Kannan’s theorem.

Second, their proofs exploit a quirk of PV and the other theories that they have symbols for all polynomial-time programs without having commensurate command of the semantics of what these programs represent. The induction and axioms available to {S_2^1} and {T_2^1} bridge some but not all of these gaps.

Third and most particular, their theorem uses a self-referential strategy. It starts building {\varphi'} but branches according to whether the theory {T} can prove {\Upsilon_{\varphi'}}. If not it keeps going, if yes it does something else. Thus the proof does not tell what {\varphi(x)} is, nor identify a particular language in {\mathcal{C}} for which the LBI property is consistent.

Open Problems

Another way of saying “Statement {\Upsilon} is consistent with {T}” is that one can build a model of {T} in which {\Upsilon} is true. What do those models look like? Do they relate to the notion of oracles {A} relative to which certain statements—such as {\mathsf{NP}^A} having languages that are (length-based-) immune to {\mathsf{P}^A}—are true?

[William–>Willard Quine]

15 Comments leave one →
  1. May 11, 2020 7:59 am

    I am correcting here a common misconception – you don’t need a stronger theory to prove consistency, just one that is not weaker, in particular an incomparable one. Gentzen proved the consistency of PA in the theory of primitive recursive arithmetic + primitive recursive induction up to epsilon 0.

    • rjlipton permalink*
      May 11, 2020 9:45 am

      Dear thebirdreader:

      Thanks, for your comment. Yes that is correct. Thanks again.

      Best and be safe

      Dick

  2. Dean permalink
    May 11, 2020 4:04 pm

    Quine’s first name is Willard! Otherwise thanks for the great post 🙂

  3. John the Scott permalink
    May 12, 2020 5:44 pm

    “turtles all the way down” was mentioned regarding infinity regress in an essay by john locke, probably alluding to the hindu story of the world elephant standing on the backs of turtles. what did the turtles stand o?

    https://www.deseret.com/2009/12/13/20358209/joe-cannon-for-skeptics-and-believers-it-s-turtles-all-the-way-down

  4. Erfan Khaniki permalink
    May 12, 2020 9:02 pm

    The example of $2^x$ function is misleading. PV cannot prove the totality of this function.

    • rjlipton permalink*
      May 14, 2020 11:31 am

      Dear Erfan Khaniki:

      Right you are. Did not mean to mislead. It can get the equations but cannot prove more powerful facts. Thanks.

      Best and be safe

      Dick

  5. Lukasz permalink
    May 13, 2020 4:10 am

    Referring to the issue of provability consistency of the Arithmetic System, I would like to inform that in the paper: T. J. Stępień, Ł. T. Stępień, „On the Consistency of the Arithmetic System”, Journal of Mathematics and System Science, vol. 7, 43 (2017), arXiv:1803.11072 , a proof of the consistency of the Arithmetic System was published (this proof had been done within this Arithmetic System). The abstract of this paper: T. J. Stepien and L. T. Stepien, “On the consistency of Peano’s Arithmetic System” , The Bulletin of Symbolic Logic , vol. 16, No. 1, 132 (2010). http://www.math.ucla.edu/~asl/bsl/1601-toc.htm .

  6. erfan khaniki permalink
    May 13, 2020 5:11 pm

    The exponentiation function example is misleading. PV cannot prove the totality of 2^x.

  7. Ivan Gusev permalink
    May 14, 2020 12:19 am

    I think my new logic gives good answer, how they might have look like. Maybe like sets of numbers with defining subset of unnatural prime numbers. I finally finished my work on making new logic when I applied it to a Proof complexity theory. I must appologize for my outrageous pretentiousness but I believe it is the key. It is very intresting to me, will this allow anyone to bypass all known barriers and what is difference between observer and oracle. Unfortunaly, I started to write it right before falling asleep and it took some time, so I didn’t find the way of translating definitions but I believe google-translate can do it more or less perfectly for you. If something is unclear I can comment tomorrow.

    Аксиомы логики взаимоопределения / List of axioms of the logic of mutual determinations(=definitions)

    1)
    Eng. Information exist in two states in respect to observer — declorative and selfsustaining.
    РЯЗ. Информация существует в двух формах относительно наблюдателя — Декларативная и Асимметричная(самодостаточная).

    Определение: Декларативное ядро — это набор информации, которая содержит данные и конечное количество правил, которые способны представить для наблюдателя эволюцию системы с любого выбранного состояния в любое другое состояние возможное для выбранной системы. (Декларативное ядро не может использовать асимметричную информацию для поддержки собственной непротиворечивости.)

    2)
    Eng. Everything is (always) defined by something.
    РЯЗ. Любая информация всегда порождена информацией.

    Определение: Элемент — это данные конечного размера, которые могут встречаться в системе и имеют структурированность позволяющую различить конечному набору правил один из них от другого.

    Определение: Цепочка разлогающего наблюдения — это бесконечная(зацикленность допустима) иерархизированная цепочка из элементов, каждый из которых ссылается на порождающие его элементы системы с помощью применений к нему некоторого количество правил самодостаточной информации.

    Замечание: Если декларативное ядро не способно описать элемент в рамках своих правил или требует применение к нему бесконечного количества правил для выведения его из других элементов, то элемент имеет асимметрические свойства по отношению к своему наблюдателю.

    3)
    Eng. Mechanics of the observer are defined by the system he is being in.
    РЯЗ. Наблюдатель всегда определён своей системой, вся информация которая определяет его, его наблюдения, механизм их восприятия, принадлежит его системе.

    4)
    Eng. Observer is ensealed under his observations.
    РЯЗ. Наблюдатель способен видеть только ту информацию, которая порождена для него его наблюдениями.

    5)
    Eng. Any change to a state of a system is always governed by an act of mutual determination.
    РЯЗ. Любое изменение данных описывающих систему всегда определено только и только актом взаимоопределения.

    Определение: Урэлемент — это некоторое абстрактное объединение свойств, взаимосовпадение/взаимодействие которых у двух или более урэлементов во время акта взаимоопределения приводит к манифестации этого свойства как явного свойства системы, которую они пораждают.

    Определение: Акт взаимоопределения — это событие изменения информационной полноты определённой системы во время её эволюции и изначального структурированного порождения.

    6)
    Eng. Observer can’t observe urelements directly but he can guess them.
    РЯЗ. Наблюдение Урэлементов наблюдателем невозможно.

    7)
    Eng. Evolution of the system is impossible without acts of MD.
    РЯЗ. Без взаимоопределения эволюция системы невозможна.

    Главный вопрос логики взаимоопределения: «Каково множество Урэлементов, которое необходимо для успешного порождения системы и её эволюции при котором любой выбранный наблюдатель был бы способен породить декларативное ядро с помощью которого был бы способен произвести вычисление её эволюции самостоятельно и достаточное для ответа на его вопрос?»

    Main question of this logic is: “What is the nature of set of urelements that is needed for succesful generation of the system and its evolution under which any chosen observer would be capable of having his own declorative core that would allow him to compute evolution of the system enough to answer his question”

    Main usage of LoMD occurs in proof complexity theory. Suppose we have problem P and we want to know what is a complexity of computation M that is needed to compute fact of existence of another computation C that decides problem R while abiding property T. Then we can take a look at P and its all sets of urelements under LoMD and choose one with the least complexity(or use my street magic of Diffs with Topology tricks to avoid this entirely), after that we can convert urelements to prime numbers while introducing our local version of fundamental theorem of Arithmetics for them and our local L-Function. When we got that we can study complexity of + and * operation in our set replacing question of proof complexity by question of complexity of operators. HERE YOU MUST PROVE RIEMANN HYPOTHESIS or just assume that it is true to proceed further. To measure complexity of operators you must take a look at your number set like it is dynamical system, it allows you to use LoMD again, You can simply replace addition with descrete evolution of the system and multiplication by CAUSALITY. Using it you can find line of past-future contracts that yelds a universal measurment for any observer. If your observer tries to predict evolution of the system he MUST read certain contract from that line that will help him to distinguish all local events from any other local event from another time. Such a trick yelds complexity of the proof by amount of the data your contract has to contain plus complexity of reading it. Studying properties of different prelocked properties T with different problems P yields P!=NP. The logic can be used in variety of ways, though. My goal is proof complexity now.

  8. May 14, 2020 12:25 pm

    Nice post.
    For length-based immunity,
    “Definition 2 A language {B} is length-based immune (LBI) to {\mathsf{P}} if for every polynomial-time program {P_i}, there are only finitely many {n} such that {P_i} is correct on strings of length {n}.”

    The qualification phrase “only finitely many {n}” is redundant and misleading, as the set of strings of length {n} for any {n} must be finite.

  9. May 23, 2020 6:56 pm

    I like “P=NP” in title. I know Lipton knows the truth.

  10. Stella Seremetaki Mathematician permalink
    June 6, 2020 12:20 pm

    Reblogged this on Magazino.

  11. Serge permalink
    June 11, 2020 5:28 am

    Are there inconsistent theories in which a contradiction is so hard to prove that they look consistent? Could it be the case that both “P=NP” and “P≠NP” are provable, though incredibly hard to prove?

    • rjlipton permalink*
      June 11, 2020 9:19 am

      Dear Serge:

      Thanks for this insightful question. There has been work on theorems like: The theorem T may be inconsistent, but there is no “short” proof that 0=1. Not sure if this is useful, but people have thought about this.

      Best and be safe

      Dick

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s