Universality for Nondeterministic Logspace
Universality for Nondeterministic Logspace
复制标题
非确定性对数空间的普遍性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Somenath Biswas
中科院分区：
文献类型：
--
作者：
Vinay Choudhary;A. Sinha;Somenath Biswas
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
