Search results for "NP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
1	Zhiyao Liang, Rakesh M. Verma	Correcting and Improving the NP Proof for Cryptographic Protocol Insecurity.	ICISS	2009	DBLP DOI BibTeX RDF	insecurity, Cryptographic protocols, secrecy, NP
1	Gábor Kun, Mario Szegedy	A new line of attack on the dichotomy conjecture.	STOC	2009	DBLP DOI BibTeX RDF	term operations, computational complexity, constraint satisfaction problems, fourier analysis, NP, dichotomy
1	Parikshit Gopalan, Venkatesan Guruswami	Hardness Amplification within NP against Deterministic Algorithms.	CCC	2008	DBLP DOI BibTeX RDF	Hardness Amplication, Error-Correcting Codes, Derandomization, NP
1	Morteza Moniri	Preservation theorems for bounded formulas.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Polynomial induction, Model completeness, Universal theory, Quantifier elimination, Intuitionistic logic, NP, Bounded arithmetic, Polynomial hierarchy, Kripke model
1	Gábor Kun, Jaroslav Nesetril	NP by Means of Lifts and Shadows.	MFCS	2007	DBLP DOI BibTeX RDF	duality, Constraint Satisfaction Problem, homomorphism, Digraph, NP
1	Abdullah N. Arslan	A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings.	FCT	2007	DBLP DOI BibTeX RDF	common subsequence, multi-dimensional string, dynamic programming, image, NP
1	Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender	Complexity of finite-horizon Markov decision process problems.	J. ACM	2000	DBLP DOI BibTeX RDF	NPPP, computational complexity, Markov decision processes, NP, PL, partially observable Markov decision processes, PSPACE, succinct representations
1	Thomas Eiter, Yuri Gurevich, Georg Gottlob	Existential second-order logic over strings.	J. ACM	2000	DBLP DOI BibTeX RDF	S1S, existential fragment, finite satisfiability, finite words, prefix classes, model checking, strings, regular languages, descriptive complexity, finite model theory, decision problem, NP, second-order logic
1	Christoph Ambühl	Offline List Update is NP-Hard.	ESA	2000	DBLP DOI BibTeX RDF	list-update, competitive analysis, On-line algorithms, NP
1	John H. Reif	Parallel Biomolecular Computation: Models and Simulations.	Algorithmica	1999	DBLP DOI BibTeX RDF	Parallel RAM, Nondeterministic computation, Recombinant DNA, Parallel computation, DNA, NP, Biomolecular computation, Biotechnology
1	Jin-yi Cai, D. Sivakumar, Martin Strauss 0001	Constant Depth Circuits and the Lutz Hypothesis.	FOCS	1997	DBLP DOI BibTeX RDF	Lutz hypothesis, Exponential Time, constant-depth, nearly exponential-size circuits, circuit complexity theory, computational complexity, pseudorandom generators, complexity classes, NP, constant depth circuits
1	Ashish V. Naik, Alan L. Selman	A Note on P-selective sets and on Adaptive versus Nonadaptive Queries to NP.	CCC	1996	DBLP DOI BibTeX RDF	P, p-selective, adaptive reductions, nonadaptive reductions, complexity classes, NP
1	Georg Gottlob	NP Trees and Carnap's Modal Logic.	J. ACM	1995	DBLP DOI BibTeX RDF	bounded query computation, trees, modal logic, oracle, epistemic logic, NP, autoepistemic logic
1	Johan Håstad	The shrinkage exponent is 2	FOCS	1993	DBLP DOI BibTeX RDF	shrinkage exponent, random restriction, explicit function, NP
1	Sanjeev Arora, Shmuel Safra	Probabilistic Checking of Proofs; A New Characterization of NP	FOCS	1992	DBLP DOI BibTeX RDF	membership proofs, languages, time complexity, polynomial time, independent set, clique, NP
1	Sanjeev Arora, Carsten Lund, Rajeev Motwani 0001, Madhu Sudan 0001, Mario Szegedy	Proof Verification and Hardness of Approximation Problems	FOCS	1992	DBLP DOI BibTeX RDF	approximation problems, polynomial-time probabilistic oracle machine, random bits, MAXSNP-hard, metric TSP, time complexity, NP, MAX-CUT, MAX-SAT, proof verification
1	Oded Goldreich 0001, Silvio Micali, Avi Wigderson	Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.	J. ACM	1991	DBLP DOI BibTeX RDF	fault tolerant distributed computing, methodological design of protocols, cryptographic protocols, zero-knowledge, graph isomorphism, one-way functions, proof systems, NP, interactive proofs
1	Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser	Languages that Are Easier than their Proofs	FOCS	1991	DBLP DOI BibTeX RDF	nonrandom self-reducible sets, triple-exponential time, incoherent sets, formal languages, membership, NP, DSPACE
1	Mike Paterson, Uri Zwick	Shrinkage of de~Morgan formulae under restriction	FOCS	1991	DBLP DOI BibTeX RDF	de Morgan formulae, random restriction, induced function, lower bound, NP
1	Ker-I Ko	Computational Complexity of Roots of Real Functions (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	roots of real functions, one-to-one, k-to-one functions, discrete complexity classes, LOGSPACE, P, UP, classification, computational complexity, NP
1	Takumi Kasai, Akeo Adachi, Shigeki Iwata	Classes of pebble games and complete problems.	ACM Annual Conference (2)	1978	DBLP DOI BibTeX RDF	Exponential time, Log-space, Two-person game, Winning strategy, Polynomial time, Turing machine, NP, Pebble game, Polynomial space