-creative sets are a family of formal languages in the complexity class NP whose complements certifiably do not have
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.
-creative sets, the lack of a (more restricted) recognition algorithm can be proven, whereas a proof that NP ≠ co-NP remains elusive.
-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.
[2][3] 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
This notation should be distinguished with that for the complexity class NP.
The complexity class NP is a set of formal languages, while
Every language in NP is recognized by a program in one of the sets
in the bound on the number of steps) the exponent in the polynomial running time of the program.
More formally, there should exist a polynomially computable function
that maps programs in this class to inputs on which they fail.
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
This disallows, for instance, functions that take polynomial time but produce outputs of less than polynomial length.
This number of steps (on that input) would be consistent with
and its accepting path, and then verify that the input equals
-creative set with a polynomially honest productive function is NP-complete.
that ignores its own input and instead searches for a witness for
, accepting its input if it finds one and rejecting otherwise.
long enough (but still polynomial) for its running time to qualify for membership in
[2] 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
to larger equivalent instances that encode the "irrelevant" information
-creative languages having these permutations as their productive functions provide candidate counterexamples to the Berman–Hartmanis conjecture.
The conjecture states that there exists a one-way length-increasing function
[2] Alan Selman observed that this would imply a simpler conjecture, the encrypted complete set conjecture: there exists a one-way function
[5] There exists an oracle relative to which one-way functions exist, both of these conjectures are false, and the Berman–Hartmanis conjecture is true.