The difference and truth-table hierarchies for NP
RAIRO-Theor. Inf. Appl., 21 4 (1987) 419-435
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
620 (2023)
https://doi.org/10.1109/ICIT58056.2023.10226089
Acceptance in incomplete argumentation frameworks
Dorothea Baumeister, Matti Järvisalo, Daniel Neugebauer, Andreas Niskanen and Jörg RotheArtificial Intelligence 295 103470 (2021)
https://doi.org/10.1016/j.artint.2021.103470
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
Toniann Pitassi, Morgan Shirley and Thomas Watsoncomputational complexity 30 (2) (2021)
https://doi.org/10.1007/s00037-021-00210-5
On Turing Machines Deciding According to the Shortest Computations
Florin ManeaAxioms 10 (4) 304 (2021)
https://doi.org/10.3390/axioms10040304
Emptiness problems for integer circuits
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler and Marc TechnauTheoretical Computer Science 824-825 11 (2020)
https://doi.org/10.1016/j.tcs.2020.03.023
Individual resource games and resource redistributions
Nicolas TroquardJournal of Logic and Computation 30 (5) 1023 (2020)
https://doi.org/10.1093/logcom/exaa031
Efficient algorithms for membership in boolean hierarchies of regular languages
Christian Glaßer, Heinz Schmitz and Victor SelivanovTheoretical Computer Science 646 86 (2016)
https://doi.org/10.1016/j.tcs.2016.07.017
Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
Anja Rey, Jörg Rothe, Hilmar Schadrack and Lena SchendAnnals of Mathematics and Artificial Intelligence 77 (3-4) 317 (2016)
https://doi.org/10.1007/s10472-015-9461-y
The Complexity of Computing Minimal Unidirectional Covering Sets
Dorothea Baumeister, Felix Brandt, Felix Fischer, Jan Hoffmann and Jörg RotheTheory of Computing Systems 53 (3) 467 (2013)
https://doi.org/10.1007/s00224-012-9437-9
Mind change speed-up for learning languages from positive data
Sanjay Jain and Efim KinberTheoretical Computer Science 489-490 37 (2013)
https://doi.org/10.1016/j.tcs.2013.04.009
Fine hierarchies via Priestley duality
Victor SelivanovAnnals of Pure and Applied Logic 163 (8) 1075 (2012)
https://doi.org/10.1016/j.apal.2011.12.029
Counting classes and the fine structure between NC1 and L
Samir Datta, Meena Mahajan, B.V. Raghavendra Rao, Michael Thomas and Heribert VollmerTheoretical Computer Science 417 36 (2012)
https://doi.org/10.1016/j.tcs.2011.05.050
Mathematical Foundations of Computer Science 2010
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas and Heribert VollmerLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2010 6281 306 (2010)
https://doi.org/10.1007/978-3-642-15155-2_28
FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
VICTOR SELIVANOVInternational Journal of Foundations of Computer Science 19 (03) 649 (2008)
https://doi.org/10.1142/S0129054108005875
The boolean hierarchy of NP-partitions
Sven Kosub and Klaus W. WagnerInformation and Computation 206 (5) 538 (2008)
https://doi.org/10.1016/j.ic.2007.06.003
Fine hierarchies and m-reducibilities in theoretical computer science
Victor L. SelivanovTheoretical Computer Science 405 (1-2) 116 (2008)
https://doi.org/10.1016/j.tcs.2008.06.031
The complexity of unions of disjoint sets
Christian Glaßer, Alan L. Selman, Stephen Travers and Klaus W. WagnerJournal of Computer and System Sciences 74 (7) 1173 (2008)
https://doi.org/10.1016/j.jcss.2008.05.001
STACS 2007
Christian Glaßer, Alan L. Selman, Stephen Travers and Klaus W. WagnerLecture Notes in Computer Science, STACS 2007 4393 248 (2007)
https://doi.org/10.1007/978-3-540-70918-3_22
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
Edith Hemaspaandra, Jörg Rothe and Holger SpakowskiRAIRO - Theoretical Informatics and Applications 40 (1) 75 (2006)
https://doi.org/10.1051/ita:2005041
Error-bounded probabilistic computations between MA and AM
Elmar Böhler, Christian Glaßer and Daniel MeisterJournal of Computer and System Sciences 72 (6) 1043 (2006)
https://doi.org/10.1016/j.jcss.2006.05.001
Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries
Edith Hemaspaandra, Lane A. Hemaspaandra and Harald HempelSIAM Journal on Computing 34 (6) 1352 (2005)
https://doi.org/10.1137/S0097539701391002
Exact complexity of Exact-Four-Colorability
Jörg RotheInformation Processing Letters 87 (1) 7 (2003)
https://doi.org/10.1016/S0020-0190(03)00229-1
Discrete Mathematics and Theoretical Computer Science
Sven KosubLecture Notes in Computer Science, Discrete Mathematics and Theoretical Computer Science 2731 225 (2003)
https://doi.org/10.1007/3-540-45066-1_18
STACS 2003
Harry Buhrman, Richard Chang and Lance FortnowLecture Notes in Computer Science, STACS 2003 2607 547 (2003)
https://doi.org/10.1007/3-540-36494-3_48
SIGACT news complexity theory column 35
Lane A. HemaspaandraACM SIGACT News 33 (1) 32 (2002)
https://doi.org/10.1145/507457.507465
Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph
Richard Beigel, Lane A. Hemaspaandra, Harald Hempel and Jörg VogelInformation and Computation 173 (2) 123 (2002)
https://doi.org/10.1006/inco.2001.3072
On boolean lowness and boolean highness
Steffen Reith and Klaus W. WagnerTheoretical Computer Science 261 (2) 305 (2001)
https://doi.org/10.1016/S0304-3975(00)00146-8
STACS 2000
Sven Kosub and Klaus W. WagnerLecture Notes in Computer Science, STACS 2000 1770 157 (2000)
https://doi.org/10.1007/3-540-46541-3_13
Mathematical Foundations of Computer Science 2000
Sven KosubLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2000 1893 467 (2000)
https://doi.org/10.1007/3-540-44612-5_42
Mathematical Foundations of Computer Science 2000
Edith Hemaspaandra and Lane A. HemaspaandraLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2000 1893 64 (2000)
https://doi.org/10.1007/3-540-44612-5_5
STACS 99
Edith Hemaspaandra, Lane. A. Hemaspaandra and Harald HempelLecture Notes in Computer Science, STACS 99 1563 270 (1999)
https://doi.org/10.1007/3-540-49116-3_25
Generalized Quantifiers and Computation
Iain A. StewartLecture Notes in Computer Science, Generalized Quantifiers and Computation 1754 51 (1999)
https://doi.org/10.1007/3-540-46583-9_3
A note on parallel queries and the symmetric-difference hierarchy
Klaus W. WagnerInformation Processing Letters 66 (1) 13 (1998)
https://doi.org/10.1016/S0020-0190(98)00024-6
The structure of logarithmic advice complexity classes
JoséL. Balcázar and Montserrat HermoTheoretical Computer Science 207 (1) 217 (1998)
https://doi.org/10.1016/S0304-3975(98)00066-8
A Downward Collapse within the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra and Harald HempelSIAM Journal on Computing 28 (2) 383 (1998)
https://doi.org/10.1137/S0097539796306474
Computing and Combinatorics
Steffen Reith and Klaus W. WagnerLecture Notes in Computer Science, Computing and Combinatorics 1449 147 (1998)
https://doi.org/10.1007/3-540-68535-9_18
Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
Edith Hemaspaandra and Jörg RotheInformation Processing Letters 65 (3) 151 (1998)
https://doi.org/10.1016/S0020-0190(97)00219-6
Query Order
Lane A. Hemaspaandra, Harald Hempel and Gerd WechsungSIAM Journal on Computing 28 (2) 637 (1998)
https://doi.org/10.1137/S0097539796297632
Algorithms and Complexity
Edith Hemaspaandra, Lane A. Hemaspaandra and Harald HempelLecture Notes in Computer Science, Algorithms and Complexity 1203 49 (1997)
https://doi.org/10.1007/3-540-62592-5_60
Exact analysis of Dodgson elections
Edith Hemaspaandra, Lane A. Hemaspaandra and Jörg RotheJournal of the ACM 44 (6) 806 (1997)
https://doi.org/10.1145/268999.269002
Fundamentals of Computation Theory
Edith Hemaspaandra, Lane A. Hemaspaandra and Harald HempelLecture Notes in Computer Science, Fundamentals of Computation Theory 1279 222 (1997)
https://doi.org/10.1007/BFb0036186
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
Lane A. Hemaspaandra and Jörg RotheSIAM Journal on Computing 26 (3) 634 (1997)
https://doi.org/10.1137/S0097539794261970
Oracles That Compute Values
Stephen Fenner, Steven Homer, Mitsunori Ogihara and Alan SelmanSIAM Journal on Computing 26 (4) 1043 (1997)
https://doi.org/10.1137/S0097539793247439
Automata, Languages and Programming
Edith Hemaspaandra, Lane A. Hemaspaandra and Jörg RotheLecture Notes in Computer Science, Automata, Languages and Programming 1256 214 (1997)
https://doi.org/10.1007/3-540-63165-8_179
STACS 97
Edith Hemaspaandra, Lane A. Hemaspaandra and Harald HempelLecture Notes in Computer Science, STACS 97 1200 319 (1997)
https://doi.org/10.1007/BFb0023469
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
J. Castro and C. SearaRAIRO - Theoretical Informatics and Applications 30 (2) 101 (1996)
https://doi.org/10.1051/ita/1996300201011
Upper bounds for the complexity of sparse and tally descriptions
V. Arvind, J. Köbler and M. MundhenkMathematical Systems Theory 29 (1) 63 (1996)
https://doi.org/10.1007/BF01201814
198 (1996)
https://doi.org/10.1109/CCC.1996.507682
206 (1995)
https://doi.org/10.1109/SCT.1995.514859
On computing Boolean connectives of characteristic functions
R. Chang and J. KadinMathematical Systems Theory 28 (3) 173 (1995)
https://doi.org/10.1007/BF01303054
Generalized theorems on relationships among reducibility notions to certain complexity classes
Mitsunori OgiwaraMathematical Systems Theory 27 (3) 189 (1994)
https://doi.org/10.1007/BF01578841
Complexity-Restricted Advice Functions
Johannes Köbler and Thomas ThieraufSIAM Journal on Computing 23 (2) 261 (1994)
https://doi.org/10.1137/S0097539791200351
A taxonomy of complexity classes of functions
Alan L. SelmanJournal of Computer and System Sciences 48 (2) 357 (1994)
https://doi.org/10.1016/S0022-0000(05)80009-1
Computer Science Logic
Iain A. StewartLecture Notes in Computer Science, Computer Science Logic 702 410 (1993)
https://doi.org/10.1007/3-540-56992-8_25
A relationship between difference hierarchies and relativized polynomial hierarchies
Richard Beigel, Richard Chang and Mitsunori OgiwaraMathematical Systems Theory 26 (3) 293 (1993)
https://doi.org/10.1007/BF01371729
STACS 93
Stephen Fenner, Steve Homer, Mitsunori Ogiwara and Alan L. SelmanLecture Notes in Computer Science, STACS 93 665 398 (1993)
https://doi.org/10.1007/3-540-56503-5_40
Algorithms and Computation
V. Arvind, J. Köbler and M. MundhenkLecture Notes in Computer Science, Algorithms and Computation 650 249 (1992)
https://doi.org/10.1007/3-540-56279-6_78
Probabilistic polynomial time is closed under parity reductions
Richard Beigel, Lane A. Hemachandra and Gerd WechsungInformation Processing Letters 37 (2) 91 (1991)
https://doi.org/10.1016/0020-0190(91)90140-D
On adaptive versus nonadaptive bounded query machines
Ker-I KoTheoretical Computer Science 82 (1) 51 (1991)
https://doi.org/10.1016/0304-3975(91)90171-W
Bounded queries to SAT and the Boolean hierarchy
Richard BeigelTheoretical Computer Science 84 (2) 199 (1991)
https://doi.org/10.1016/0304-3975(91)90160-4
On truth-table reducibility to SAT
Samuel R. Buss and Louise HayInformation and Computation 91 (1) 86 (1991)
https://doi.org/10.1016/0890-5401(91)90075-D
305 (1990)
https://doi.org/10.1109/SCT.1990.113979
Bounded Query Classes
Klaus W. WagnerSIAM Journal on Computing 19 (5) 833 (1990)
https://doi.org/10.1137/0219058
Bounded query classes and the difference hierarchy
Richard Beigel, William I. Gasarch and Louise HayArchive for Mathematical Logic 29 (2) 69 (1989)
https://doi.org/10.1007/BF01620618
On Sets Truth-Table Reducible to Sparse Sets
Ronald V. Book and Ker-I KoSIAM Journal on Computing 17 (5) 903 (1988)
https://doi.org/10.1137/0217056