- Length-Increasing Reductions for PSPACE-Completeness
2013/01/01 by John M. Hitchcock, A. Pavan · 1 citation
Computer Science · Mathematics · #Advice (programming) #Algorithm #Combinatorics #Completeness (order theory) #Complexity and Algorithms in Graphs #Complexity class #Computational complexity theory #Computer science #Discrete mathematics #Exponential function #Machine Learning and Algorithms #Mathematical proof #Mathematics #Oracle #PSPACE #Pigeonhole principle #Pseudorandom number generator #Randomness #Statistics #Structural complexity theory #Time complexity #semigroups and automata theory
- Settling the complexity of computing two-player Nash equilibria
2009/05/01 by Xi Chen, Xiaotie Deng, Shang-Hua Teng +1 · 83 citations
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Class (philosophy) #Combinatorics #Complexity class #Computer science #Discrete mathematics #Economic theories and models #Game Theory and Applications #Game Theory and Voting Systems #Game theory #Mathematical economics #Mathematics #Nash equilibrium #Polynomial #Time complexity
- The Computational Complexity of Tutte Invariants for Planar Graphs
2005/01/01 by Dirk Vertigan · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #semigroups and automata theory #Complexity and Algorithms in Graphs #Combinatorics #Tutte polynomial #Mathematics #Planar graph #Corollary #Discrete mathematics #Planar #Algebraic number #Computational complexity theory #Complexity class #Enumeration #Time complexity #Graph #Computer science #Algorithm #Line graph #Voltage graph
- Generic-case complexity, decision problems in group theory, and random walks
2003/05/12 by Ilya Kapovich, Alexei Myasnikov, Paul E. Schupp +2 · 1 citation
Mathematics · #Advanced Operator Algebra Research #Algorithm #Artificial intelligence #Class (philosophy) #Combinatorics #Complexity class #Computer science #Conjugacy class #Conjugacy problem #Decision problem #Discrete mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Group (periodic table) #Mathematics #Random walk #Time complexity
- Complexity of finite-horizon Markov decision process problems
2000/07/01 by Martin Mundhenk, Judy Goldsmith, Christopher Lusena +1 · 14 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Applied mathematics #Complexity class #Computational complexity theory #Computer science #Decision problem #Machine Learning and Algorithms #Markov decision process #Markov process #Mathematical optimization #Mathematical proof #Mathematics #Observability #Optimization and Search Problems #Succinctness #Theoretical computer science #Time complexity
- Probabilistic checking of proofs
1998/01/01 by Sanjeev Arora, Muli Safra · 12 citations
Computer Science · Mathematics · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Formal Methods in Verification #Mathematical proof #Characterization (materials science) #Clique #Class (philosophy) #Logarithm #Discrete mathematics #Probabilistic logic #Mathematics #Combinatorics #Set (abstract data type) #Time complexity #Complexity class #Computer science #Statistics
- Natural Proofs
1997/08/01 by Alexander Razborov, Alexander A Razborov, Steven Rudich · 7 citations
Computer Science · Mathematics · #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Complexity class #Computer science #Cryptography and Data Security #Discrete mathematics #Function (biology) #Logarithm #Machine Learning and Algorithms #Mathematical proof #Mathematics #Natural number #Time complexity #Upper and lower bounds
- Recursion theory on the reals and continuous-time computation
1996/08/01 by Cristopher Moore · 1 citation
Computer Science · Mathematics · #Algebra over a field #Algebraic number #Algorithm #Arithmetic function #Cellular Automata and Applications #Class (philosophy) #Complexity class #Computability theory #Computability, Logic, AI Algorithms #Computable function #Computation #Computer science #Discrete mathematics #Hierarchy #Mathematics #Mutual recursion #Number theory #Numerical Methods and Algorithms #Operator (biology) #Primitive recursive function #Pure mathematics #Recursion (computer science) #Recursive functions #Theory of computation #Time complexity #μ operator
- Approximating probabilistic inference in Bayesian belief networks is NP-hard
1993/03/01 by Paul Dagum, Michael Luby · 57 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Approximate inference #Artificial intelligence #Bayesian Modeling and Causal Inference #Bayesian inference #Bayesian network #Bayesian probability #Class (philosophy) #Complexity class #Computational complexity theory #Computer science #Discrete mathematics #Graphical model #Inference #Machine Learning and Algorithms #Mathematics #Polynomial #Probabilistic analysis of algorithms #Probabilistic logic #Theoretical computer science #Time complexity
- NP-Complete decision problems for binary quadratics
1978/04/01 by Kenneth L. Manders, Leonard M. Adleman, Leonard Adleman · 1 citation
Computer Science · Mathematics · #Algorithm #Combinatorics #Complexity class #Computability, Logic, AI Algorithms #Computational complexity theory #Decision problem #Degree (music) #Discrete mathematics #Logic, programming, and type systems #Mathematics #Modulo #NP #Natural number #Nondeterministic algorithm #P versus NP problem #PSPACE #Time complexity #Turing machine #Variable (mathematics) #semigroups and automata theory