Search

Your search keyword '"Structural complexity theory"' showing total 18 results
Start Over Descriptor "Structural complexity theory" Publisher cambridge university press
18 results on '"Structural complexity theory"'

1. Representation Theory and Its Uses in Complexity Theory

Author

Joseph M. Landsberg

Subjects
Combinatorics, Structural complexity theory, Theoretical computer science, Computer science, Theory of computation, C-minimal theory, Game complexity, Descriptive complexity theory, Representation theory, Quantum complexity theory
Published
2017
Full Text
View/download PDF

3. Main theorems and definitions

Author

Sanjeev Arora and Boaz Barak

Subjects
Algebra, Discrete mathematics, PH, Average-case complexity, Structural complexity theory, Asymptotic computational complexity, Computational problem, Descriptive complexity theory, Computational resource, Mathematics, Quantum complexity theory
Published
2009
Full Text
View/download PDF

4. Fundamental problems in proof complexity

Author

Jan Krajíček

Subjects
Algebra, Average-case complexity, Discrete mathematics, Structural complexity theory, Forcing (recursion theory), Proof complexity, Complexity class, Descriptive complexity theory, Probabilistically checkable proof, Mathematics, Quantum complexity theory
Published
2010
Full Text
View/download PDF

5. TWO-SORTED LOGIC AND COMPLEXITY CLASSES

Author

Phuong Nguyen and Stephen A. Cook

Subjects
Discrete mathematics, PH, Structural complexity theory, Theoretical computer science, Proof complexity, Proof theory, Structural proof theory, Non-classical logic, Descriptive complexity theory, Mathematics, Quantum complexity theory
Published
2010
Full Text
View/download PDF

6. THE THEORY V 1 AND POLYNOMIAL TIME

Author

Phuong Nguyen and Stephen A. Cook

Subjects
PH, Discrete mathematics, Structural complexity theory, Proof theory, Proof complexity, Proof by contradiction, Complexity class, Structural proof theory, Descriptive complexity theory, Mathematics
Published
2010
Full Text
View/download PDF

7. Interactive proofs

Author

Boaz Barak and Sanjeev Arora

Subjects
Structural complexity theory, Theoretical computer science, NEXPTIME, Computational complexity theory, Asymptotic computational complexity, Descriptive complexity theory, Computational problem, Computational resource, Algorithm, Mathematics, Quantum complexity theory
Published
2009
Full Text
View/download PDF

8. The polynomial hierarchy and alternations

Author

Sanjeev Arora and Boaz Barak

Subjects
PH, Polynomial hierarchy, Discrete mathematics, Structural complexity theory, Theoretical computer science, Fast-growing hierarchy, EXPTIME, Asymptotic computational complexity, Complexity class, Descriptive complexity theory, Mathematics
Published
2009
Full Text
View/download PDF

9. Circuit lower bounds: Complexity theory's Waterloo

Author

Sanjeev Arora and Boaz Barak

Subjects
Discrete mathematics, Algebra, Structural complexity theory, ACC0, Computational complexity theory, Algorithmics, Asymptotic computational complexity, Circuit complexity, Computational geometry, Symbolic computation, Mathematics
Published
2009
Full Text
View/download PDF

10. About this book

Author

Boaz Barak and Sanjeev Arora

Subjects
PH, Average-case complexity, Structural complexity theory, Theoretical computer science, Computer science, Asymptotic computational complexity, Worst-case complexity, Computational problem, Computational resource, Quantum complexity theory
Published
2009
Full Text
View/download PDF

11. Bibliography

Author

Sanjeev Arora and Boaz Barak

Subjects
PH, Computational topology, Structural complexity theory, Theoretical computer science, Computer science, Asymptotic computational complexity, Worst-case complexity, Computational problem, Computational resource, Quantum complexity theory
Published
2009
Full Text
View/download PDF

12. Diagonalization

Author

Sanjeev Arora and Boaz Barak

Subjects
PH, Structural complexity theory, DTIME, Computational complexity theory, 2-EXPTIME, Computer science, Complexity class, Computational problem, Computational resource, Algorithm
Published
2009
Full Text
View/download PDF

13. Average case complexity: Levin's theory

Author

Sanjeev Arora and Boaz Barak

Subjects
Average-case complexity, PH, Discrete mathematics, Structural complexity theory, Complete, Complexity class, Asymptotic computational complexity, Parameterized complexity, Mathematics, Quantum complexity theory
Published
2009
Full Text
View/download PDF

14. Epilogue

Author

Oded Goldreich

Subjects
Average-case complexity, PH, Structural complexity theory, Theoretical computer science, Computer science, Worst-case complexity, Asymptotic computational complexity, Computational problem, Computational resource, Quantum complexity theory
Published
2008
Full Text
View/download PDF

15. Complexity theory

Author

William A. Dembski

Subjects
Structural complexity theory, Proof calculus, business.industry, Frequentist inference, Worst-case complexity, Inference, Artificial intelligence, Descriptive complexity theory, Algorithmic inference, business, Mathematics, Quantum complexity theory
Published
1998
Full Text
View/download PDF

16. Communication Complexity

Author

Noam Nisan and Eyal Kushilevitz

Subjects
Structural complexity theory, Theoretical computer science, Computer science, Asymptotic computational complexity, Worst-case complexity, Game complexity, Descriptive complexity theory, Communication complexity, Notation, Decision tree model
Published
1996
Full Text
View/download PDF

17. The Complexity of Algorithms

Author

Michael M. Atkinson

Subjects
Structural complexity theory, Recursion, Asymptotic computational complexity, Worst-case complexity, Subject (philosophy), Probabilistic analysis of algorithms, Abstract data type, Symbolic computation, Algorithm, Mathematics
Abstract

The modern theory of algorithms dates from the late 1960s when the method of asymptotic execution time measurement began to be used. It is argued that the subject has both an engineering and scientific wing. The engineering wing consists of well-understood design methodologies while the scientific wing is concerned with theoretical underpinnings. The key issues of both wings are surveyed. Finally some personal opinions on where the subject will go next are offered.

Published
1996
Full Text
View/download PDF

18. Monotone Complexity

Author

Michelangelo Grigni and Michael Sipser

Subjects
Average-case complexity, Combinatorics, Complexity index, PH, Discrete mathematics, Structural complexity theory, Boolean circuit, Circuit complexity, Descriptive complexity theory, Boolean function, Mathematics
Published
1992
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results