Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
97 | Manuel Bodirsky, Martin Grohe |
Non-dichotomies in Constraint Satisfaction Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP (2) ![In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, pp. 184-196, 2008, Springer, 978-3-540-70582-6. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
87 | Michael Krüger, Harald Hempel |
Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ISAAC ![In: Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings, pp. 243-252, 2006, Springer, 3-540-49694-7. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
coNP-completeness, inverse NP-problems, 3-DIMENSIONAL MATCHING, computational complexity, HAMILTONIAN CYCLE |
87 | Fritz Henglein, Jakob Rehof |
The Complexity of Subtype Entailment for Simple Types. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29 - July 2, 1997, pp. 352-361, 1997, IEEE Computer Society, 0-8186-7925-5. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
subtype entailment complexity, atomic entailment, coNP-completeness, complexity-theoretic marker, exponential explosion, subtype inference, structural complexity bounds, computability, satisfiability, axiomatization, linear-time algorithm |
75 | S. J. Gismondi, E. R. Swart |
A model of the coNP-complete non-Hamilton tour decision problem for directed graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Math. Program. ![In: Math. Program. 100(3), pp. 471-483, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
Extended formulation, Assignment polytope, coNP, Projection, Hamiltonicity |
73 | Tadeusz Litak, Frank Wolter |
All Finitely Axiomatizable Tense Logics of Linear Time Flows Are CoNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Stud Logica ![In: Stud Logica 81(2), pp. 153-165, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
frame incompleteness, computational complexity, temporal logic, NP-completeness, tense logic |
61 | Alan L. Selman, Samik Sengupta |
Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pp. 82-90, 2004, IEEE Computer Society, 0-7695-2120-7. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
61 | Arnaud Durand 0001, Miki Hermann, Laurent Juban |
On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1999, 24th International Symposium, MFCS'99, Szklarska Poreba, Poland, September 6-10, 1999, Proceedings, pp. 92-102, 1999, Springer, 3-540-66408-4. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
51 | Rachel J. Harding, Patrick Bermudez, Alexander Bernier, Michael J. S. Beauvais, Pierre Bellec, Sean L. Hill, Agah Karakuzu, Bartha M. Knoppers, Paul Pavlidis, Jean-Baptiste Poline, Jane Roskams, Nikola Stikov, Jessica Stone, Stephen C. Strother, CONP Consortium, Alan C. Evans |
The Canadian Open Neuroscience Platform - An open science framework for the neuroscience community. ![Search on Bibsonomy](Pics/bibsonomy.png) |
PLoS Comput. Biol. ![In: PLoS Comput. Biol. 19(7), 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
50 | Foto N. Afrati, Phokion G. Kolaitis |
Repair checking in inconsistent databases: algorithms and complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICDT ![In: Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, pp. 31-41, 2009, ACM, 978-1-60558-423-2. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
coNP-complete problem, equality-generating dependencies, repair checking, tuple-generating dependencies, weakly acyclic set, polynomial time, consistent query answering, inconsistent databases, database repairs |
49 | Titus Dose |
P-Optimal Proof Systems for Each Set in coNP and no Complete Problems in NP⋂coNP Relative to an Oracle. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1910.08571, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
48 | Lefteris M. Kirousis, Phokion G. Kolaitis |
On the Complexity of Model Checking and Inference in Minimal Models. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LPNMR ![In: Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, pp. 42-53, 2001, Springer, 3-540-42593-4. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
48 | Harry Buhrman, Leen Torenvliet |
Complicated Complementations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 227-236, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Oracles, Kolmogorov Complexity, Complexity Classes, Simplicity, Polynomial Hierarchy, Immunity |
48 | Edith Hemaspaandra, Gerd Wechsung |
The Minimization Problem for Boolean Formulas. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pp. 575-584, 1997, IEEE Computer Society, 0-8186-8197-7. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
computational complexity, minimization, propositional logic, Boolean formulas, polynomial hierarchy |
48 | Tomasz Imielinski, Kumar V. Vadaparty |
Complexity of Query Processing in Databases with OR-Objects. ![Search on Bibsonomy](Pics/bibsonomy.png) |
PODS ![In: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania, USA, pp. 51-65, 1989, ACM Press, 0-89791-308-6. The full citation details ...](Pics/full.jpeg) |
1989 |
DBLP DOI BibTeX RDF |
|
38 | Merlijn Sevenster, Tero Tulenheimo |
Partially Ordered Connectives and Sum11 on Finite Models. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CiE ![In: Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings, pp. 516-525, 2006, Springer, 3-540-35466-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
Henkin quantifiers, partially ordered connectives, NP vs. coNP, finite model theory |
37 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 1-7, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
hard sets, polynomial advice, instance complexity |
37 | Dorit Aharonov, Oded Regev 0001 |
Lattice problems in NP cap coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 52(5), pp. 749-765, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
Algorithms, approximation, lattices, Fourier series |
37 | Dorit Aharonov, Oded Regev 0001 |
Lattice Problems in NP cap coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pp. 362-371, 2004, IEEE Computer Society, 0-7695-2228-9. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
37 | Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
All Superlinear Inverse Schemes Are coNP-Hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, pp. 368-379, 2004, Springer, 3-540-22823-3. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
37 | Arnaud Durand 0001, Miki Hermann |
The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, pp. 451-462, 2003, Springer, 3-540-00623-0. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
36 | Holger Dell, Dieter van Melkebeek |
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 251-260, 2010, ACM, 978-1-4503-0050-6. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
arithmetic progression free sets, hereditary graph properties, vertex deletion problems, satisfiability, kernelization, vertex cover, parameterized complexity, probabilistically checkable proofs, feedback vertex set, sparsification |
36 | Baris Sertkaya |
Towards the Complexity of Recognizing Pseudo-intents. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICCS ![In: Conceptual Structures: Leveraging Semantic Technologies, 17th International Conference on Conceptual Structures, ICCS 2009, Moscow, Russia, July 26-31, 2009. Proceedings, pp. 284-292, 2009, Springer, 978-3-642-03078-9. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
36 | Baris Sertkaya |
Some Computational Problems Related to Pseudo-intents. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICFCA ![In: Formal Concept Analysis, 7th International Conference, ICFCA 2009, Darmstadt, Germany, May 21-24, 2009, Proceedings, pp. 130-145, 2009, Springer, 978-3-642-01814-5. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
36 | Lance Fortnow, Rahul Santhanam |
Infeasibility of instance compression and succinct PCPs for NP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 133-142, 2008, ACM, 978-1-60558-047-0. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
instance compression, succinct PCPs, cryptography, parameterized complexity, polynomial hierarchy |
36 | Paolo Liberatore |
Complexity results on DPLL and resolution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Log. ![In: ACM Trans. Comput. Log. 7(1), pp. 84-107, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
Davis-Putnam, NP-completeness, propositional satisfiability |
36 | Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
The complexity of quantitative concurrent parity games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 678-687, 2006, ACM Press, 0-89871-605-5. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
36 | Adi Akavia, Oded Goldreich 0001, Shafi Goldwasser, Dana Moshkovitz |
On basing one-way functions on NP-hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 701-710, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
adaptive versus non-adaptive machines, reductions, one-way functions, interactive proof systems, average-case complexity |
36 | Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara |
Competing Provers Yield Improved Karp-Lipton Collapse Results. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, pp. 535-546, 2003, Springer, 3-540-00623-0. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
36 | Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer |
Equivalence and Isomorphism for Boolean Constraint Satisfaction. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 16th International Workshop, CSL 2002, 11th Annual Conference of the EACSL, Edinburgh, Scotland, UK, September 22-25, 2002, Proceedings, pp. 412-426, 2002, Springer, 3-540-44240-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
36 | Antonín Kucera 0001 |
On Simulation-Checking with Sequential Systems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ASIAN ![In: Advances in Computing Science - ASIAN 2000, 6th Asian Computing Science Conference, Penang, Malaysia, November 25-27, 2000, Proceedings, pp. 133-148, 2000, Springer, 3-540-41428-2. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
36 | Thomas Schwentick |
Padding and the Expressive Power of Existential Second-Order Logics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 11th International Workshop, CSL '97, Annual Conference of the EACSL, Aarhus, Denmark, August 23-29, 1997, Selected Papers, pp. 461-477, 1997, Springer, 3-540-64570-5. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
26 | Hans Raj Tiwary |
On the hardness of minkowski addition and related operations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SCG ![In: Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pp. 306-309, 2007, ACM, 978-1-59593-705-6. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
coNP-hardness, extended convex hull, polytope intersection, computational geometry, polytopes, turing reduction, minkowski addition |
26 | László Babai, Lance Fortnow, Carsten Lund |
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pp. 16-25, 1990, IEEE Computer Society, 0-8186-2082-X. The full citation details ...](Pics/full.jpeg) |
1990 |
DBLP DOI BibTeX RDF |
efficient provability, multiple prover interactive proof systems, two-prover interactive protocols, noncommunicating provers, randomizing polynomial-time verifier, coNP-complete languages, nondeterministic exponential time, polynomial time |
26 | Wen-Guey Tzeng |
The Equivalence and Learning of Probabilistic Automata (Extended Abstract) ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pp. 268-273, 1989, IEEE Computer Society, 0-8186-1982-1. The full citation details ...](Pics/full.jpeg) |
1989 |
DBLP DOI BibTeX RDF |
learning protocol, coNP, learning, polynomial-time algorithm, upper bound, equivalence, covering, probabilistic automata, nondeterministic finite automata |
24 | Akanksha Agrawal 0001, Henning Fernau, Philipp Kindermann, Kevin Mann, Uéverton S. Souza |
Recognizing well-dominated graphs is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 183, pp. 106419, January 2024. The full citation details ...](Pics/full.jpeg) |
2024 |
DBLP DOI BibTeX RDF |
|
24 | Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai |
Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR23, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP BibTeX RDF |
|
24 | Lev Gordeev, Edward Hermann Haeusler |
Proofs of Equalities NP = coNP = PSPACE: Simplification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2311.17939, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
24 | Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai |
Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2023, pp. 1972, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP BibTeX RDF |
|
24 | Tiziano Dalmonte, Andrea Mazzullo |
CoNP Complexity for Combinations of Non-normal Modal Logics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TABLEAUX ![In: Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Prague, Czech Republic, September 18-21, 2023, Proceedings, pp. 302-321, 2023, Springer, 978-3-031-43512-6. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
24 | Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai |
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pp. 1243-1256, 2023, ACM, 978-1-4503-9913-5. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
24 | Sanja Lukumbuzya, Magdalena Ortiz 0001, Mantas Simkus |
On the Expressive Power of Ontology-Mediated Queries: Capturing coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Description Logics ![In: Proceedings of the 36th International Workshop on Description Logics (DL 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning (KR 2023 and NMR 2023)., Rhodes, Greece, September 2-4, 2023., 2023, CEUR-WS.org. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP BibTeX RDF |
|
24 | Johannes Thürauf |
Deciding the feasibility of a booking in the European gas market is coNP-hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Ann. Oper. Res. ![In: Ann. Oper. Res. 318(1), pp. 591-618, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
24 | Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer |
Oracle with P=NP∩coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2203.11079, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
24 | Akanksha Agrawal 0001, Henning Fernau, Philipp Kindermann, Kevin Mann, Uéverton S. Souza |
Recognizing well-dominated graphs is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2208.08864, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
24 | Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer |
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria., pp. 45:1-45:15, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-256-3. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
24 | Richard Mayr, Sven Schewe, Patrick Totzke, Dominik Wojtczak |
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2101.06989, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
24 | Edward Hermann Haeusler |
Yet another argument in favour of NP=CoNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2101.00003, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
24 | Richard Mayr, Sven Schewe, Patrick Totzke, Dominik Wojtczak |
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FoSSaCS ![In: Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Luxembourg City, Luxembourg, March 27 - April 1, 2021, Proceedings, pp. 427-447, 2021, Springer, 978-3-030-71994-4. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
24 | |
Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1903.11860, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
24 | Titus Dose |
P≠NP and All Sets in NP∪coNP Have P-Optimal Proof Systems Relative to an Oracle. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1909.02839, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
24 | Jean-Camille Birget |
The word problem of the Brin-Thompson groups is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1902.03852, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
24 | |
Complete Disjoint CoNP-Pairs but No Complete Total Polynomial Search Problems Relative to an Oracle. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FCT ![In: Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings, pp. 153-167, 2019, Springer, 978-3-030-25026-3. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
24 | Zhe Chen 0011 |
Parametric runtime verification is NP-complete and coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 123, pp. 14-20, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
24 | Peter Bürgisser, Matthias Christandl, Ketan D. Mulmuley, Michael Walter 0005 |
Membership in Moment Polytopes is in NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 46(3), pp. 972-991, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
24 | Pawel Parys |
Weak containment for partial words is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 116(2), pp. 125-127, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
24 | Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jirí Matousek 0001, Emo Welzl |
A zero-player graph game in NP $\cap$ coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1605.03546, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
24 | Przemyslaw Uznanski |
All Permutations Supersequence is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1506.05079, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
24 | Peter Bürgisser, Matthias Christandl, Ketan D. Mulmuley, Michael Walter 0005 |
Membership in moment polytopes is in NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1511.03675, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
24 | Pontus Ekberg, Wang Yi 0001 |
Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ECRTS ![In: 27th Euromicro Conference on Real-Time Systems, ECRTS 2015, Lund, Sweden, July 8-10, 2015, pp. 281-286, 2015, IEEE Computer Society, 978-1-4673-7570-2. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
24 | Pontus Ekberg, Wang Yi 0001 |
Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
RTSS ![In: 2015 IEEE Real-Time Systems Symposium, RTSS 2015, San Antonio, Texas, USA, December 1-4, 2015, pp. 87-95, 2015, IEEE Computer Society, 978-1-4673-9507-6. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
24 | Stephen P. Jordan |
Strong equivalence of reversible circuits is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Quantum Inf. Comput. ![In: Quantum Inf. Comput. 14(15-16), pp. 1302-1307, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
24 | Marzio De Biasi |
Minimal TSP Tour is coNP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1403.3431, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP BibTeX RDF |
|
24 | Nerio Borges, Blai Bonet |
Universal First-Order Logic is Superfluous for NL, P, NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Log. Methods Comput. Sci. ![In: Log. Methods Comput. Sci. 10(1), 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
24 | Jérôme Leroux, Vincent Penelle, Grégoire Sutre |
The Context-Freeness Problem Is coNP-Complete for Flat Counter Systems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ATVA ![In: Automated Technology for Verification and Analysis - 12th International Symposium, ATVA 2014, Sydney, NSW, Australia, November 3-7, 2014, Proceedings, pp. 248-263, 2014, Springer, 978-3-319-11935-9. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
24 | Stephen P. Jordan |
Strong equivalence of reversible circuits is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1307.0836, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP BibTeX RDF |
|
24 | Ping Lu 0007, Feifei Peng, Haiming Chen |
Deciding Determinism of Unary Languages Is coNP-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Developments in Language Theory ![In: Developments in Language Theory - 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, pp. 350-361, 2013, Springer, 978-3-642-38770-8. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP DOI BibTeX RDF |
|
24 | Harald Hempel, Michael Krüger |
Inverse Hamiltonian Cycle and inverse 3Dimensional Matching are coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 426, pp. 49-65, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|
24 | Jan Krajícek |
On the Proof Complexity of the Nisan-Wigderson Generator based on a Hard NP ∩ coNP function. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Math. Log. ![In: J. Math. Log. 11(1), 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
24 | Christian Glaßer, Christian Reitwießner, Victor L. Selivanov |
The shrinking property for NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 412(8-10), pp. 853-864, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
24 | M. A. Shalu, S. Vijayakumar |
The Two Bicliques Problem is in NP intersection coNP ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1104.3463, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP BibTeX RDF |
|
24 | |
BPP is in NP and coNP ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1102.4346, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP BibTeX RDF |
|
24 | Vikraman Arvind, Jacobo Torán |
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 2(2), pp. 4:1-4:22, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
24 | Shun'ichi Amano |
On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 110(17), pp. 753-756, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
24 | Dmitry Gavinsky, Alexander A. Sherstov |
A Separation of NP and coNP in Multiparty Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. ![In: Theory Comput. 6(1), pp. 227-245, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
24 | Dmitry Gavinsky, Alexander A. Sherstov |
A Separation of NP and coNP in Multiparty Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR10, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
24 | Jan Krajícek |
On the proof complexity of the Nisan-Wigderson generator based on a hard NP cap coNP function. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR10, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
24 | Dmitry Gavinsky, Alexander A. Sherstov |
A Separation of NP and coNP in Multiparty Communication Complexity ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1004.0817, 2010. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
24 | Friedrich Eisenbrand, Thomas Rothvoß |
EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp. 1029-1034, 2010, SIAM, 978-0-89871-701-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
24 | Mikhail A. Babin, Sergei O. Kuznetsov |
Recognizing Pseudo-intents is coNP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CLA ![In: Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, Spain, October 19-21, 2010, pp. 294-301, 2010, CEUR-WS.org. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
24 | Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron |
P Systems with Elementary Active Membranes: Beyond NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Int. Conf. on Membrane Computing ![In: Membrane Computing - 11th International Conference, CMC 2010, Jena, Germany, August 24-27, 2010. Revised Selected Papers, pp. 338-347, 2010, Springer, 978-3-642-18122-1. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
24 | Hunter Monroe |
Speedup for Natural Problems and coNP?=NP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR09, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP BibTeX RDF |
|
24 | Hunter Monroe |
Speedup for Natural Problems and NP=?coNP ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/0906.3765, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP BibTeX RDF |
|
24 | Christian Glaßer, Christian Reitwießner, Victor L. Selivanov |
The Shrinking Property for NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR08, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP BibTeX RDF |
|
24 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR08, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP BibTeX RDF |
|
24 | Christian Glaßer, Christian Reitwießner, Victor L. Selivanov |
The Shrinking Property for NP and coNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CiE ![In: Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008, Proceedings, pp. 210-220, 2008, Springer, 978-3-540-69405-2. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
24 | Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran |
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 385(1-3), pp. 167-178, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
24 | Jean-Camille Birget |
Circuits, the Groups of Richard Thompson, and Conp-completeness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Int. J. Algebra Comput. ![In: Int. J. Algebra Comput. 16(1), pp. 35-90, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
24 | |
coNP Is Equal To NP ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/cs/0611147, 2006. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP BibTeX RDF |
|
24 | Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
All superlinear inverse schemes are coNP-hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 345(2-3), pp. 345-358, 2005. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
24 | N. V. Vinodchandran |
AMexp[nsube](NP[cap]coNP)/poly. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 89(1), pp. 43-47, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
24 | Vikraman Arvind, Jacobo Torán |
Solvable Group Isomorphism is (almost) in NP\cap coNP ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR04, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
24 | Alan L. Selman, Samik Sengupta |
Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR04, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
24 | Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
All Superlinear Inverse Schemes are coNP-Hard ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR cs.CC/0410023, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
24 | Morteza Moniri |
Comparing Constructive Arithmetical Theories Based on NP-PIND and coNP-PIND. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Log. Comput. ![In: J. Log. Comput. 13(6), pp. 881-888, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
24 | David L. Rhodes, Wayne H. Wolf |
Two CoNP-Complete Schedule Analysis Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Int. J. Found. Comput. Sci. ![In: Int. J. Found. Comput. Sci. 12(5), pp. 565-580, 2001. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
24 | Shuichi Miyazaki, Kazuo Iwama |
Approximation of coNP sets by NP-complete sets and its applications. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Syst. Comput. Jpn. ![In: Syst. Comput. Jpn. 30(7), pp. 47-54, 1999. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
24 | Kazuo Iwama, Shuichi Miyazaki |
Approximation of coNP Sets by NP-complete Sets. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, First Annual International Conference, COCOON '95, Xi'an, China, August 24-26, 1995, Proceedings, pp. 11-20, 1995, Springer, 3-540-60216-X. The full citation details ...](Pics/full.jpeg) |
1995 |
DBLP DOI BibTeX RDF |
|
24 | Juris Hartmanis, Neil Immerman |
On Complete Problems for NP$\cap$CoNP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 12th Colloquium, Nafplion, Greece, July 15-19, 1985, Proceedings, pp. 250-259, 1985, Springer, 3-540-15650-X. The full citation details ...](Pics/full.jpeg) |
1985 |
DBLP DOI BibTeX RDF |
|
24 | Michael Bauland, Edith Hemaspaandra |
Isomorphic Implication. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 44(1), pp. 117-139, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
Computational complexity, Constraints, Propositional logic, Logic in computer science, Isomorphism problem |
24 | Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo |
Kernel Bounds for Disjoint Cycles and Disjoint Paths. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESA ![In: Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, pp. 635-646, 2009, Springer, 978-3-642-04127-3. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|