Polynomial Creativity

In computational complexity theory, polynomial creativity is a theory analogous to the theory of creative sets in recursion theory and mathematical logic. The are a family of formal languages in the complexity class NP whose complements certifiably do not have nondeterministic recognition algorithms. It is generally believed that NP is unequal to co-NP (the class of complements of languages in NP), which would imply more strongly that the complements of all NP-complete languages do not have polynomial-time nondeterministic recognition algorithms. However, for the sets, the lack of a (more restricted) recognition algorithm can be proven, whereas a proof that remains elusive.

The sets are conjectured to form counterexamples to the Berman–Hartmanis conjecture on isomorphism of NP-complete sets. It is NP-complete to test whether an input string belongs to any one of these languages, but no polynomial time isomorphisms between all such languages and other NP-complete languages are known. Polynomial creativity and the sets were introduced in 1985 by Deborah Joseph and Paul Young, following earlier attempts to define polynomial analogues for creative sets by Ko and

Definition

Intuitively, a set is creative when there is a polynomial-time algorithm that creates a counterexample for any candidate fast nondeterministic recognition algorithm for its complement.

The classes of fast nondeterministic recognition algorithms are formalized by Joseph and Young as the sets $\mathrm^$ of nondeterministic Turing machine programs $p$ that, for inputs $x$ that they accept, have an accepting path with a number of steps that is at most This notation should be distinguished with that for the complexity class NP. The complexity class NP is a set of formal languages, while $\mathrm^$ is instead a set of programs that accept some of these languages. Every language in NP is recognized by a program in one of the sets with a parameter $k$ that is (up to the factor $, p,$ in the bound on the number of steps) the exponent in the polynomial running time of the

According to Joseph and Young's theory, a language $L$ in NP is if it is possible to find a witness showing that the complement of $L$ is not recognized by any program
More formally, there should exist a polynomially computable function $f$ that maps programs in this class to inputs on which they fail. When given a
nondeterministic program $p$ the function $f$ should produce an input string $x=f(p)$ that either belongs to $L$ and causes the program to or does not belong to $L$ and causes the program to The function $f$ is called a ''productive function'' If this productive function exists, the given program does not produce the behavior on input $x$ that would be expected of a program for recognizing the complement

Existence

Joseph and Young define a polynomial-time function $f$ to be ''polynomially honest'' if its running time is at most a polynomial function of its output length. This disallows, for instance, functions that take polynomial time but produce outputs of less than polynomial length. As they show, every one-to-one polynomially-honest function $f$ is the productive function for a

Joseph and Young define $K_f^k$ to be the set of values $f(p)$ for nondeterministic programs $p$ that have an accepting path for $f(p)$ using at most $, p, (, f(p), ^k+1)$ steps. This number of steps (on that input) would be consistent with $p$ belonging Then $K_f^k$ belongs to NP, for given an input $f(p)$ one can nondeterministically guess both $p$ and its accepting path, and then verify that the input equals $f(p)$ and that the path is valid

Language $K_f^k$ is with $f$ as its productive function, because every program $p$ in $\mathrm^$ is mapped by $f$ to a value $f(p)$ that is either accepted by $p$ (and therefore also belongs to $K_f^k$) or rejected by $p$ (and therefore also does not belong

Completeness

Every set with a polynomially honest productive function is NP-complete. For any other language $X$ in NP, by the definition of NP, one can translate any input $x$ for $X$ into a nondeterministic program $p_x$ that ignores its own input and instead searches for a witness accepting its input if it finds one and rejecting otherwise. The length of $p_x$ is polynomial in the size of $x$ and a padding argument can be used to make $p_x$ long enough (but still polynomial) for its running time to qualify for membership Let $f$ be the productive function used to define a given and let $g$ be the translation from $x$ Then the composition of $g$ with $f$ maps inputs of $X$ into counterexamples for the algorithms that test those inputs. This composition maps inputs that belong to $X$ into strings that belong and inputs that do not belong to $X$ into strings that do not belong Thus, it is a polynomial-time many-one reduction from $X$ Since $L$ is (by definition) in NP, and every other language in NP has a reduction to it, it must be

It is also possible to prove more strongly that there exists an invertible parsimonious reduction to the

Application to the Berman–Hartmanis conjecture

The Berman–Hartmanis conjecture states that there exists a polynomial-time isomorphism between any two NP-complete sets: a function that maps yes-instances of one such set one-to-one into yes-instances of the other, takes polynomial time, and whose inverse function can also be computed in polynomial time. It was formulated by Leonard C. Berman and Juris Hartmanis in 1977, based on the observation that all NP-complete sets known at that time were isomorphic.
An equivalent formulation of the conjecture is that every NP-complete set is ''paddable''. This means that there exists a polynomial-time and polynomial-time-invertible one-to-one transformation $h(x,y)$ from yes-instances $x$ to larger yes-instances that encode the "irrelevant"

However, it is unknown how to find such a padding transformation for a language whose productive function is not polynomial-time-invertible. Therefore, if one-way permutations exist, the languages having these permutations as their productive functions provide candidate counterexamples to the Berman–Hartmanis

The (unproven) Joseph–Young conjecture formalizes this reasoning. The conjecture states that there exists a one-way length-increasing function $f$ such that $K_f^k$ is not paddable. Alan Selman observed that this would imply a simpler conjecture, the ''encrypted complete set conjecture'': there exists a one-way function $f$ such that $\mathrm$ (the set of yes-instances for the satisfiability problem) and $f(\mathrm)$ are
There exists an oracle relative to which one-way functions exist, both of these conjectures are false, and the Berman–Hartmanis conjecture is

References

{{reflist, refs=

{{citation
, last1 = Berman , first1 = L.
, last2 = Hartmanis , first2 = J. , author2-link = Juris Hartmanis
, issue = 2
, journal = SIAM Journal on Computing
, mr = 0455536
, pages = 305–322
, title = On isomorphisms and density of NP and other complete sets
, volume = 6
, year = 1977 , doi=10.1137/0206023, hdl = 1813/7101
, url = https://ecommons.cornell.edu/bitstream/1813/7101/1/75-260.pdf
, hdl-access = free

{{citation, title=P, NP, and NP-Completeness: The Basics of Computational Complexity, first=Oded, last=Goldreich, author-link=Oded Goldreich, publisher=Cambridge University Press, year=2010, isbn=9781139490092, page
154–155
}

{{citation
, last1 = Joseph , first1 = Deborah , author1-link = Deborah Joseph
, last2 = Young , first2 = Paul
, doi = 10.1016/0304-3975(85)90140-9
, issue = 2–3
, journal = Theoretical Computer Science
, mr = 821203
, pages = 225–237
, title = Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
, volume = 39
, year = 1985, url = http://digital.library.wisc.edu/1793/58504 , doi-access = free

{{citation
, last1 = Ko , first1 = Ker-I
, last2 = Moore , first2 = Daniel
, doi = 10.1137/0210061
, issue = 4
, journal = SIAM Journal on Computing
, mr = 635436
, pages = 787–796
, title = Completeness, approximation and density
, volume = 10
, year = 1981

{{citation
, last = Rogers , first = John
, doi = 10.1006/jcss.1997.1486
, issue = 3
, journal = Journal of Computer and System Sciences
, mr = 1463764
, pages = 412–423
, title = The isomorphism conjecture holds and one-way functions exist relative to an oracle
, volume = 54
, year = 1997, doi-access = free

{{citation
, last = Selman , first = Alan L. , author-link = Alan Selman
, doi = 10.1007/BF01374525
, issue = 3
, journal = Mathematical Systems Theory
, mr = 1151339
, pages = 203–221
, title = A survey of one-way functions in complexity theory
, volume = 25
, year = 1992, s2cid = 33642595

Structural complexity theory