- On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
2023/12/18 by Marcus Gozon, Gozon, Marcus, Jingjin Yu +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Manufacturing and Logistics Optimization #Algorithm #Artificial Intelligence (cs.AI) #Computational complexity theory #Computer science #Constant (computer programming) #FOS: Computer and information sciences #Geometry #Mathematical optimization #Mathematics #Modular Robots and Swarm Intelligence #Multiagent Systems (cs.MA) #Optimization and Search Problems #PSPACE #Robotics (cs.RO) #Square (algebra) #Tile #Time complexity
- On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses
2016/09/01 by Catalin-Valeriu Lita · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Biology #Bounded function #Combinatorics #Computational complexity theory #Computer science #DNA and Biological Computing #Discrete mathematics #Formalism (music) #Grammar #Linguistics #Mathematics #PSPACE #Philosophy #Theoretical computer science #semigroups and automata theory
- Exact algorithms for maximum independent set
2013/12/21 by Mingyu Xiao, Hiroshi Nagamochi · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computational complexity theory #Computer science #Degree (music) #Discrete mathematics #Exponential function #Graph #Independent set #Mathematics #Maximal independent set #PSPACE #Set (abstract data type) #Time complexity #Vertex (graph theory) #cs.DS
- 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
- A Note on Exact Algorithms for Vertex Ordering Problems on Graphs
2011/01/20 by Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster +2 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems #Travelling salesman problem #Vertex (graph theory) #Combinatorics #Mathematics #Time complexity #Discrete mathematics #PSPACE #Space (punctuation) #Algorithm #Graph #Computer science #Computational complexity theory
- Saving space by algebraization
2010/06/05 by Daniel Lokshtanov, Jesper Nederlof · 2 citations
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Knapsack problem #Time complexity #Polynomial #Mathematics #Polynomial-time approximation scheme #PSPACE #Space (punctuation) #Continuous knapsack problem #Matrix polynomial #Reciprocal polynomial #Discrete mathematics #Combinatorics #Computational complexity theory #Algebra over a field #Computer science #Algorithm #Pure mathematics #Mathematical analysis
- Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances
2009/09/05 by Paul Bonsma, Luis Cereceda · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bipartite graph #Combinatorics #Computational complexity theory #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Optimization and Search Problems #PSPACE #Planar graph #Vertex (graph theory)
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
2007/12/13 by Andreas Björklund, Thore Husfeldt · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Discrete mathematics #Exponential function #Exponential time hypothesis #Graph #Hypergraph #Mathematics #Optimization and Search Problems #PSPACE #Partition (number theory) #Satisfiability #Time complexity #Vertex (graph theory) #Vertex cover
- Improved Parameterized Upper Bounds for Vertex Cover
2006/01/01 by Jianer Chen, Iyad A. Kanj, Iyad Kanj +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Cover (algebra) #Discrete mathematics #Exponential function #Graph #Mathematical analysis #Mathematics #PSPACE #Parameterized complexity #Polynomial #Polynomial and algebraic computation #Space (punctuation) #Time complexity #Upper and lower bounds #Vertex (graph theory) #Vertex cover
- Entropy rates and finite-state dimension
2005/10/11 by Chris Bourke, John M. Hitchcock, N. V. Vinodchandran +1 · 3 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Combinatorics #Computability, Logic, AI Algorithms #Computational complexity theory #Discrete mathematics #Entropy (arrow of time) #Entropy rate #Joint quantum entropy #Mathematical analysis #Mathematics #PSPACE #Physics #Principle of maximum entropy #Quantum mechanics #Statistics #Upper and lower bounds #semigroups and automata theory
- Counting models for 2SAT and 3SAT formulae
2004/11/18 by Vilhelm Dahllöf, Peter Jonsson, Peter Jönsson +1 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Boolean satisfiability problem #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Data Management and Algorithms #Discrete mathematics #Mathematics #PSPACE #Polynomial #Satisfiability #Separable space #Time complexity #True quantified Boolean formula
- Approximating clique is almost NP-complete
2002/12/09 by Uriel Feige, S. Goldwasser, László Lovász +2 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Chordal graph #Clique #Clique problem #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete mathematics #EXPTIME #Graph #Machine Learning and Algorithms #Mathematics #Omega #PSPACE #Pathwidth #Philosophy #Treewidth
- On polynomial-time Turing and many-one completeness in PSPACE
1992/04/01 by Osamu Watanabe, Shouwen Tang · 1 citation
Computer Science · Mathematics · #Algorithm #Combinatorics #Completeness (order theory) #Computability, Logic, AI Algorithms #Computational complexity theory #Discrete mathematics #Logic, Reasoning, and Knowledge #Mathematical analysis #Mathematics #PSPACE #semigroups and automata theory
- The complexity of propositional linear temporal logics
1985/07/01 by A. P. Sistla, A. Prasad Sistla, E. M. Clarke · 39 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Algorithm #Artificial intelligence #Computational complexity theory #Computer science #Description logic #Discrete mathematics #Intermediate logic #Linear temporal logic #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Monoidal t-norm logic #PSPACE #Propositional calculus #Propositional variable #Satisfiability #T-norm fuzzy logics #Theoretical computer science #Well-formed formula
- A probabilistic PDL
1985/04/01 by Dexter Kozen · 13 citations
Computer Science · Mathematics · #Algorithm #Calculus (dental) #Computational complexity theory #Computer science #Discrete mathematics #Formal Methods in Verification #Intermediate logic #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #PSPACE #Probabilistic CTL #Probabilistic analysis of algorithms #Probabilistic logic #Property (philosophy) #Propositional calculus #Propositional variable #Simple (philosophy) #Space (punctuation) #Statistics #Theoretical computer science
- N by N Checkers is Exptime Complete
1984/05/01 by J. M. Robson · 2 citations
Computer Science · Social Sciences · Economics, Econometrics and Finance · Mathematics · #Artificial Intelligence in Games #Digital Games and Media #Sports Analytics and Performance #Exponential function #PSPACE #Time complexity #Position (finance) #EXPTIME #Mathematics #Function (biology) #Exponential growth #Upper and lower bounds #Exponential time hypothesis #Combinatorics #Discrete mathematics #Polynomial #Computational complexity theory #Computer science #Algorithm
- 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