Title :
Finitary substructure languages with application to the theory of NP-completeness
Author :
Regan, Kenneth W.
Author_Institution :
Cornell Math. Sci. Inst., Ithaca, NY, USA
Abstract :
Decision problems that involve the search for a fixed, finite amount of information hidden somewhere in the input are considered. In terms of polynomial complexity these finitary substructure languages (k-SLs) are much like tally sets. For instance, every k-SL A p-Turing reduces to a canonically associated set TΛ, and so cannot be NP-hard unless the polynomial hierarchy collapses to its second level. However, it is shown that k-SLs have different structural properties. Many familiar NP-complete sets equal free unions L of k-SLs Lk. An assertion that every such L is p-isomorphic to S AT is supported. It is also shown that whether A is p-T equivalent to TΛ above is tied to whether k-DNF formulas can be learned deterministically by oracle queries alone in the Valiant model. A finite-injury priority construction that highlights obstacles to establishing certain properties for recursive sets is given
Keywords :
Turing machines; computational complexity; formal languages; set theory; NP-complete sets; NP-completeness; Valiant model; finitary substructure languages; oracle queries; p-Turing; polynomial complexity; polynomial hierarchy; recursive sets; tally sets; Circuits; Contracts; Educational institutions; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41814