“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 {{mvar|k}}-creative sets are a family of formal languages in the complexity class NP whose complements certifiably do not have

-time nondeterministic recognition algorithms.

The {{mvar|k}}-creative 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 {{mvar|k}}-creative sets were introduced in 1985 by Deborah Joseph and Paul Young, following earlier attempts to define polynomial analogues for creative sets by Ko and Moore.{{r|jy|km}}

Definition

Joseph and Young define the set

to be the set of nondeterministic Turing machine programs

that, for inputs

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

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

; the parameter

is (up to the factor

in the bound on the number of steps) the exponent in the polynomial running time of the program.{{r|jy}}

According to Joseph and Young's theory, a language

in NP is {{mvar|k}}-creative if it is possible to find a witness showing that the complement of

is not recognized by any program in

More formally, there should exist a polynomially computable function

that, when given a

nondeterministic program

, finds an input

that either belongs to

and causes the program to accept

, or does not belong to

and causes the program to reject

. The function

is called a productive function for

. If this productive function exists, the given program does not produce the behavior on input

that would be expected of a program for recognizing the complement of

.{{r|jy}}

Completeness

Every

-creative set is NP-complete. For, applying a padding argument, there exists a polynomial-time translation

of the instances of any other language in NP into nondeterministic polynomial-time programs in

, such that yes-instances are translated into programs that accept all inputs and no-instances are translated into programs that reject all inputs. The composition of this translation with the function

is a polynomial-time many-one reduction from the given language to the

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

-creative set.{{r|jy}}

Existence

Joseph and Young define a polynomial-time function

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

is the productive function for a

-creative language

.{{r|jy}}

Given

, Joseph and Young define

to be the set of values

for nondeterministic programs

that have an accepting path for

using at most

steps. This number of steps (on that input) would be consistent with

belonging to

Then

belongs to NP, for given an input

one can nondeterministically guess both

and its accepting path, and then verify that the path is valid for

.{{r|jy}}

Language

-creative, with

as its productive function, because every program

is mapped by

to a value

that is either accepted by

(and therefore also belongs to

) or rejected by

(and therefore also does not belong to

).{{r|jy}}

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

from yes-instances

to larger yes-instances that encode the "irrelevant" information

.{{r|bh}}

However, it is unknown how to find such a padding transformation for a

-creative language whose productive function is not polynomial-time-invertible. Therefore, if one-way permutations exist, the

-creative languages having these permutations as their productive functions provide candidate counterexamples to the Berman–Hartmanis conjecture.{{r|jy}}

The (unproven) Joseph–Young conjecture formalizes this reasoning. The conjecture states that there exists a one-way length-increasing function

such that

is not paddable.{{r|jy}} Alan Selman observed that this would imply a simpler conjecture, the encrypted complete set conjecture: there exists a one-way function

such that

(the set of yes-instances for the satisfiability problem) and

are non-isomorphic.{{r|s}}

There exists an oracle relative to which one-way functions exist, both of these conjectures are false, and the Berman–Hartmanis conjecture is true.{{r|r}}

References

1. ^{{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}}
2. ^{{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}}
3. ^{{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}}
4. ^{{citation | last = Selman | first = Alan L. | 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}}