Optimal series-parallel trade-offs for reducing a function to its own graph
From MaRDI portal
Publication:1854508
DOI10.1006/inco.2001.3072zbMath1009.68050OpenAlexW2010338977MaRDI QIDQ1854508
Harald Hempel, Jörg Vogel, Richard Beigel, Hemaspaandra, Lane A.
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2001.3072
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- A note on enumerative counting
- On the complexity of ranking
- The complexity of optimization problems
- Bounded queries to SAT and the Boolean hierarchy
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- A taxonomy of complexity classes of functions
- Quasi-linear truth-table reductions to \(p\)-selective sets
- Some connections between bounded query classes and non-uniform complexity.
- Enumerative counting is hard
- Approximable sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Bounded Query Classes
- The difference and truth-table hierarchies for NP
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Polynomial-Time Membership Comparable Sets
This page was built for publication: Optimal series-parallel trade-offs for reducing a function to its own graph
