Universality for Nondeterministic Logspace
Vinay Choudhary, Anand Kumar Sinha, Somenath Biswas · Language and Automata Theory and Applications · 2007
The notion of universality was introduced [AB92] in 1992 in the context of NP. The major motivation of the work was to capture in a theory the essential sameness of various NPcompleteness proofs. The approach was to find out precisely what is preserved by natural reductions. When we wish to show that a language A polynomial time, many-one reduces to an NP-complete language B vis a reduction f , the reduction f needs only to preserve membership, viz., x ∈ A iff f(x) ∈ B. However, natural reductions can be seen to preserve far more than membership. The notion of universality provided precisely what remains preserved: it is the set of witnesses or solutions each witnessing x ∈ A (in the context of an NP relation RA defining the language A) that remains preserved, in the sense that from the set of witnesses witnessing f(x) ∈ B (in the context of an NP relation RB defining B) the set of witnesses witnessing x ∈ A can be extracted in a feasible manner. Finally, [AB92] also gave a structural characterization of universal NP relations.1