Search results for "coNP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
97	Manuel Bodirsky, Martin Grohe	Non-dichotomies in Constraint Satisfaction Complexity.	ICALP (2)	2008	DBLP DOI BibTeX RDF
87	Michael Krüger, Harald Hempel	Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete.	ISAAC	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.	LICS	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.	Math. Program.	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.	Stud Logica	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.	CCC	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.	MFCS	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.	PLoS Comput. Biol.	2023	DBLP DOI BibTeX RDF
50	Foto N. Afrati, Phokion G. Kolaitis	Repair checking in inconsistent databases: algorithms and complexity.	ICDT	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.	CoRR	2019	DBLP BibTeX RDF
48	Lefteris M. Kirousis, Phokion G. Kolaitis	On the Complexity of Model Checking and Inference in Minimal Models.	LPNMR	2001	DBLP DOI BibTeX RDF
48	Harry Buhrman, Leen Torenvliet	Complicated Complementations.	CCC	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.	FOCS	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.	PODS	1989	DBLP DOI BibTeX RDF
38	Merlijn Sevenster, Tero Tulenheimo	Partially Ordered Connectives and Sum11 on Finite Models.	CiE	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.	CCC	2008	DBLP DOI BibTeX RDF	hard sets, polynomial advice, instance complexity
37	Dorit Aharonov, Oded Regev 0001	Lattice problems in NP cap coNP.	J. ACM	2005	DBLP DOI BibTeX RDF	Algorithms, approximation, lattices, Fourier series
37	Dorit Aharonov, Oded Regev 0001	Lattice Problems in NP cap coNP.	FOCS	2004	DBLP DOI BibTeX RDF
37	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel	All Superlinear Inverse Schemes Are coNP-Hard.	MFCS	2004	DBLP DOI BibTeX RDF
37	Arnaud Durand 0001, Miki Hermann	The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete.	STACS	2003	DBLP DOI BibTeX RDF
36	Holger Dell, Dieter van Melkebeek	Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.	STOC	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.	ICCS	2009	DBLP DOI BibTeX RDF
36	Baris Sertkaya	Some Computational Problems Related to Pseudo-intents.	ICFCA	2009	DBLP DOI BibTeX RDF
36	Lance Fortnow, Rahul Santhanam	Infeasibility of instance compression and succinct PCPs for NP.	STOC	2008	DBLP DOI BibTeX RDF	instance compression, succinct PCPs, cryptography, parameterized complexity, polynomial hierarchy
36	Paolo Liberatore	Complexity results on DPLL and resolution.	ACM Trans. Comput. Log.	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.	SODA	2006	DBLP DOI BibTeX RDF
36	Adi Akavia, Oded Goldreich 0001, Shafi Goldwasser, Dana Moshkovitz	On basing one-way functions on NP-hardness.	STOC	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.	STACS	2003	DBLP DOI BibTeX RDF
36	Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer	Equivalence and Isomorphism for Boolean Constraint Satisfaction.	CSL	2002	DBLP DOI BibTeX RDF
36	Antonín Kucera 0001	On Simulation-Checking with Sequential Systems.	ASIAN	2000	DBLP DOI BibTeX RDF
36	Thomas Schwentick	Padding and the Expressive Power of Existential Second-Order Logics.	CSL	1997	DBLP DOI BibTeX RDF
26	Hans Raj Tiwary	On the hardness of minkowski addition and related operations.	SCG	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	FOCS	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)	FOCS	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.	Inf. Process. Lett.	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.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
24	Lev Gordeev, Edward Hermann Haeusler	Proofs of Equalities NP = coNP = PSPACE: Simplification.	CoRR	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.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
24	Tiziano Dalmonte, Andrea Mazzullo	CoNP Complexity for Combinations of Non-normal Modal Logics.	TABLEAUX	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.	STOC	2023	DBLP DOI BibTeX RDF
24	Sanja Lukumbuzya, Magdalena Ortiz 0001, Mantas Simkus	On the Expressive Power of Ontology-Mediated Queries: Capturing coNP.	Description Logics	2023	DBLP BibTeX RDF
24	Johannes Thürauf	Deciding the feasibility of a booking in the European gas market is coNP-hard.	Ann. Oper. Res.	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.	CoRR	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.	CoRR	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.	MFCS	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.	CoRR	2021	DBLP BibTeX RDF
24	Edward Hermann Haeusler	Yet another argument in favour of NP=CoNP.	CoRR	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.	FoSSaCS	2021	DBLP DOI BibTeX RDF
24		Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle.	CoRR	2019	DBLP BibTeX RDF
24	Titus Dose	P≠NP and All Sets in NP∪coNP Have P-Optimal Proof Systems Relative to an Oracle.	CoRR	2019	DBLP BibTeX RDF
24	Jean-Camille Birget	The word problem of the Brin-Thompson groups is coNP-complete.	CoRR	2019	DBLP BibTeX RDF
24		Complete Disjoint CoNP-Pairs but No Complete Total Polynomial Search Problems Relative to an Oracle.	FCT	2019	DBLP DOI BibTeX RDF
24	Zhe Chen 0011	Parametric runtime verification is NP-complete and coNP-complete.	Inf. Process. Lett.	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.	SIAM J. Comput.	2017	DBLP DOI BibTeX RDF
24	Pawel Parys	Weak containment for partial words is coNP-complete.	Inf. Process. Lett.	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.	CoRR	2016	DBLP BibTeX RDF
24	Przemyslaw Uznanski	All Permutations Supersequence is coNP-complete.	CoRR	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.	CoRR	2015	DBLP BibTeX RDF
24	Pontus Ekberg, Wang Yi 0001	Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete.	ECRTS	2015	DBLP DOI BibTeX RDF
24	Pontus Ekberg, Wang Yi 0001	Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization.	RTSS	2015	DBLP DOI BibTeX RDF
24	Stephen P. Jordan	Strong equivalence of reversible circuits is coNP-complete.	Quantum Inf. Comput.	2014	DBLP DOI BibTeX RDF
24	Marzio De Biasi	Minimal TSP Tour is coNP-Complete.	CoRR	2014	DBLP BibTeX RDF
24	Nerio Borges, Blai Bonet	Universal First-Order Logic is Superfluous for NL, P, NP and coNP.	Log. Methods Comput. Sci.	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.	ATVA	2014	DBLP DOI BibTeX RDF
24	Stephen P. Jordan	Strong equivalence of reversible circuits is coNP-complete.	CoRR	2013	DBLP BibTeX RDF
24	Ping Lu 0007, Feifei Peng, Haiming Chen	Deciding Determinism of Unary Languages Is coNP-Complete.	Developments in Language Theory	2013	DBLP DOI BibTeX RDF
24	Harald Hempel, Michael Krüger	Inverse Hamiltonian Cycle and inverse 3Dimensional Matching are coNP-complete.	Theor. Comput. Sci.	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.	J. Math. Log.	2011	DBLP DOI BibTeX RDF
24	Christian Glaßer, Christian Reitwießner, Victor L. Selivanov	The shrinking property for NP and coNP.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
24	M. A. Shalu, S. Vijayakumar	The Two Bicliques Problem is in NP intersection coNP	CoRR	2011	DBLP BibTeX RDF
24		BPP is in NP and coNP	CoRR	2011	DBLP BibTeX RDF
24	Vikraman Arvind, Jacobo Torán	Solvable Group Isomorphism Is (Almost) in NP ∩ coNP.	ACM Trans. Comput. Theory	2011	DBLP DOI BibTeX RDF
24	Shun'ichi Amano	On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
24	Dmitry Gavinsky, Alexander A. Sherstov	A Separation of NP and coNP in Multiparty Communication Complexity.	Theory Comput.	2010	DBLP DOI BibTeX RDF
24	Dmitry Gavinsky, Alexander A. Sherstov	A Separation of NP and coNP in Multiparty Communication Complexity.	Electron. Colloquium Comput. Complex.	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.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
24	Dmitry Gavinsky, Alexander A. Sherstov	A Separation of NP and coNP in Multiparty Communication Complexity	CoRR	2010	DBLP BibTeX RDF
24	Friedrich Eisenbrand, Thomas Rothvoß	EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard.	SODA	2010	DBLP DOI BibTeX RDF
24	Mikhail A. Babin, Sergei O. Kuznetsov	Recognizing Pseudo-intents is coNP-complete.	CLA	2010	DBLP BibTeX RDF
24	Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron	P Systems with Elementary Active Membranes: Beyond NP and coNP.	Int. Conf. on Membrane Computing	2010	DBLP DOI BibTeX RDF
24	Hunter Monroe	Speedup for Natural Problems and coNP?=NP.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
24	Hunter Monroe	Speedup for Natural Problems and NP=?coNP	CoRR	2009	DBLP BibTeX RDF
24	Christian Glaßer, Christian Reitwießner, Victor L. Selivanov	The Shrinking Property for NP and coNP.	Electron. Colloquium Comput. Complex.	2008	DBLP BibTeX RDF
24	Harry Buhrman, John M. Hitchcock	NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.	Electron. Colloquium Comput. Complex.	2008	DBLP BibTeX RDF
24	Christian Glaßer, Christian Reitwießner, Victor L. Selivanov	The Shrinking Property for NP and coNP.	CiE	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.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
24	Jean-Camille Birget	Circuits, the Groups of Richard Thompson, and Conp-completeness.	Int. J. Algebra Comput.	2006	DBLP DOI BibTeX RDF
24		coNP Is Equal To NP	CoRR	2006	DBLP BibTeX RDF
24	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel	All superlinear inverse schemes are coNP-hard.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
24	N. V. Vinodchandran	AMexp[nsube](NP[cap]coNP)/poly.	Inf. Process. Lett.	2004	DBLP DOI BibTeX RDF
24	Vikraman Arvind, Jacobo Torán	Solvable Group Isomorphism is (almost) in NP\cap coNP	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
24	Alan L. Selman, Samik Sengupta	Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
24	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel	All Superlinear Inverse Schemes are coNP-Hard	CoRR	2004	DBLP BibTeX RDF
24	Morteza Moniri	Comparing Constructive Arithmetical Theories Based on NP-PIND and coNP-PIND.	J. Log. Comput.	2003	DBLP DOI BibTeX RDF
24	David L. Rhodes, Wayne H. Wolf	Two CoNP-Complete Schedule Analysis Problems.	Int. J. Found. Comput. Sci.	2001	DBLP DOI BibTeX RDF
24	Shuichi Miyazaki, Kazuo Iwama	Approximation of coNP sets by NP-complete sets and its applications.	Syst. Comput. Jpn.	1999	DBLP DOI BibTeX RDF
24	Kazuo Iwama, Shuichi Miyazaki	Approximation of coNP Sets by NP-complete Sets.	COCOON	1995	DBLP DOI BibTeX RDF
24	Juris Hartmanis, Neil Immerman	On Complete Problems for NP$\cap$CoNP.	ICALP	1985	DBLP DOI BibTeX RDF
24	Michael Bauland, Edith Hemaspaandra	Isomorphic Implication.	Theory Comput. Syst.	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.	ESA	2009	DBLP DOI BibTeX RDF