Optimal series-parallel trade-offs for reducing a function to its own graph
type: Item
instance of: scholarly article
title: Optimal series-parallel trade-offs for reducing a function to its own graph
zbMATH Open document ID: 1009.68050
author: Richard Beigel
author: Harald Hempel
author: Jörg Vogel
author: Lane A. Hemaspaandra
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1853242
MaRDI profile type: Publication
full work available at URL: inco.2001.3072
OpenAlex ID: W2010338977
cites work: Quasi-linear truth-table reductions to \(p\)-selective sets
cites work: Some connections between bounded query classes and non-uniform complexity.
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: Approximable sets
cites work: Q4281494
cites work: Enumerative counting is hard
cites work: A note on enumerative counting
cites work: Q5666536
cites work: Q4218151
cites work: The strong exponential hierarchy collapses
cites work: On the complexity of ranking
cites work: The difference and truth-table hierarchies for NP
cites work: The complexity of optimization problems
cites work: A comparison of polynomial time reducibilities
cites work: Polynomial-Time Membership Comparable Sets
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: A taxonomy of complexity classes of functions
cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
cites work: Q4133140
cites work: Relative complexity of checking and evaluating
cites work: Bounded Query Classes
DOI: 10.1006/INCO.2001.3072
description: scientific article; zbMATH DE number 1853242