Finitary substructure languages with application to the theory of NP-completeness

Publisher Website
Google Scholar
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/sub Lambda /, 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 L/sub k/. 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/sub Lambda / 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.

This publication has 10 references indexed in Scilit: