Related Research Articles
Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to non-linearity, randomness, collective dynamics, hierarchy, and emergence.
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction.
Combinatorial game theory measures game complexity in several ways:
- State-space complexity,
- Game tree size,
- Decision complexity,
- Game-tree complexity,
- Computational complexity.
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also been studied for its own sake, more broadly, ideas from linear logic have been influential in fields such as programming languages, game semantics, and quantum physics, as well as linguistics, particularly because of its emphasis on resource-boundedness, duality, and interaction.
Giorgi Japaridze is a Georgian-American researcher in logic and theoretical computer science. He currently holds the title of Full Professor at the Computing Sciences Department of Villanova University. Japaridze is best known for his invention of computability logic, cirquent calculus, and Japaridze's polymodal logic.
Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.
Harlan D. Mills was Professor of Computer Science at the Florida Institute of Technology and founder of Software Engineering Technology, Inc. of Vero Beach, Florida. Mills' contributions to software engineering have had a profound and enduring effect on education and industrial practice. Since earning his Ph.D. in Mathematics at Iowa State University in 1952, Mills led a distinguished career.
Harry George Mairson is a theoretical computer scientist and professor of computer science in the Volen National Center for Complex Systems at Brandeis University in Waltham, Massachusetts. His research is in the fields of logic in computer science, lambda calculus and functional programming, type theory and constructive mathematics, computational complexity theory, and algorithmics.
In mathematics, effective dimension is a modification of Hausdorff dimension and other fractal dimensions that places it in a computability theory setting. There are several variations of which the most common is effective Hausdorff dimension. Dimension, in mathematics, is a particular way of describing the size of an object. Hausdorff dimension generalizes the well-known integer dimensions assigned to points, lines, planes, etc. by allowing one to distinguish between objects of intermediate size between these integer-dimensional objects. For example, fractal subsets of the plane may have intermediate dimension between 1 and 2, as they are "larger" than lines or curves, and yet "smaller" than filled circles or rectangles. Effective dimension modifies Hausdorff dimension by requiring that objects with small effective dimension be not only small but also locatable in a computable sense. As such, objects with large Hausdorff dimension also have large effective dimension, and objects with small effective dimension have small Hausdorff dimension, but an object can have small Hausdorff but large effective dimension. An example is an algorithmically random point on a line, which has Hausdorff dimension 0 but effective dimension 1.
Harry Roy Lewis is an American computer scientist, mathematician, and university administrator known for his research in computational logic, textbooks in theoretical computer science, and writings on computing, higher education, and technology. He is Gordon McKay Research Professor of Computer Science at Harvard University, and was Dean of Harvard College from 1995 to 2003.
Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form
Samuel R. (Sam) Buss is an American computer scientist and mathematician who has made major contributions to the fields of mathematical logic, complexity theory and proof complexity. He is currently a professor at the University of California, San Diego, Department of Computer Science and Department of Mathematics.
Benjamin E. Rossman is an American mathematician and theoretical computer scientist, specializing in computational complexity theory. He is currently an associate professor of computer science and mathematics at Duke University.
Anna Maria Zdunik is a Polish mathematician. She specializes in dynamical systems, and is a professor at the University of Warsaw.
Robyn R. Lutz is an American computer scientist whose research involves software engineering, including modeling and checking software requirements and software system safety. She is a professor of computer science at Iowa State University.
References
- ↑ Ambos-Spies, Klaus; Mayordomo, Elvira (May 2019). "Resource-bounded measure and randomness". In Sorbi, Andrea (ed.). Complexity, Logic, and Recursion Theory. CRC Press. pp. 1–47. doi:10.1201/9780429187490-1. S2CID 15041656.
In this survey we present the fundamental results of Lutz's resource-bounded measure theory
- ↑ Reimann, Jan; Stephan, Frank (2005). "Effective Hausdorff dimension". In Baaz, Matthias; Friedman, Sy-David; Krajíček, Jan (eds.). Logic Colloquium '01: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Vienna, Austria, August 6–11, 2001. Lecture Notes in Logic. Vol. 20. Association for Symbolic Logic. pp. 369–385. MR 2143904.
We continue the study of effective Hausdorff dimension as it was initiated by Lutz
- 1 2 3 "Short CV" (PDF). Retrieved 2023-04-12.
- ↑ Jack Lutz at the Mathematics Genealogy Project
- ↑ "People". Laboratory for Molecular Programming. Iowa State University. Retrieved 2023-04-12.
- ↑ Lutz, Jack H. (1987). "Acknowledgement". Resource-Bounded Category and Measure in Exponential Complexity Classes (PDF) (Doctoral dissertation). California Institute of Technology. pp. iii–iv.
- ↑ "Neil Lutz curriculum vitae" (PDF). 2021. Retrieved 2023-04-13.
- ↑ Lutz, Jack H.; Lutz, Neil; Lutz, Robyn R.; Riley, Matthew R. (May 2019). "Robustness and games against nature in molecular programming". 2019 IEEE/ACM 41st International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER). IEEE. arXiv: 1902.06171 . doi:10.1109/icse-nier.2019.00025.
