Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
From MaRDI portal
Publication:3893305
DOI10.1137/0209003zbMath0447.68044OpenAlexW2021131202MaRDI QIDQ3893305
Patrick C. Fischer, Chandra M. R. Kintala
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209003
nondeterminismrelativized classesoracle setsclass of languages acceptable by polynomial-time bounded Turing machinesrelativized polynomial-time bounded computations
Related Items
Space-efficient recognition of sparse self-reducible languages, On problems with short certificates, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], The Birth and Early Years of Parameterized Complexity, IN MEMORIAM CHANDRA KINTALA, Bounded fixed-parameter tractability and reducibility, Polynomial-time reducibilities and ``almost all oracle sets, Relativized alternation and space-bounded computation, On finding a minimum dominating set in a tournament, The emptiness problem for intersections of regular languages, On measuring nondeterminism in regular languages, Fault-tolerance and complexity (Extended abstract), The complexity of manipulative attacks in nearly single-peaked electorates, On quasilinear-time complexity theory, On the complexity of monotone dualization and generating minimal hypergraph transversals, Optimal advice, On the relation between ambiguity and nondeterminism in finite automata, Molecular computing, bounded nondeterminism, and efficient recursion, Measuring nondeterminism in pushdown automata, Monotone Boolean dualization is in co-NP\([\log^{2}n\).], On the space and circuit complexity of parameterized problems: classes and completeness, Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits, The minimum equivalent DNF problem and shortest implicants, Nondeterministics circuits, space complexity and quasigroups
