The Safe AI Problem
The Safe AI Problem is the most important unsolved question in the history of computer science.
- AI safety – The Safe AI Problem is the most important unsolved question in the history of computer science. Probably even harder than The P vs NP problem, the Safe AI Problems asks whether an AI which becomes superintelligent through the “intelligence explosion” can be controlled by humans forever and also be mathematically provably safe and beneficial for humans forever. This question has profound implications for fields such as education, stock markets, business, finance, cryptography, algorithm design, computational theory AND existential human survival. The problem is considered unsolved because no solution is known and experts in the field disagree about proposed solutions, or if a solution is even possible at all.
- Technological singularity
List of unsolved problems in computer science From Wikipedia, the free encyclopedia
This article is a list of notable unsolved problems in computer science. A problem in computer science is considered unsolved when no solution is known or when experts in the field disagree about proposed solutions.
Computational complexity
- P versus NP problem – The P vs NP problem is a major unsolved question in computer science that asks whether every problem whose solution can be quickly verified by a computer (NP) can also be quickly solved by a computer (P). This question has profound implications for fields such as cryptography, algorithm design, and computational theory.[1]
- What is the relationship between BQP and NP?
- NC = P problem
- NP = co-NP problem
- P = BPP problem
- P = PSPACE problem
- L = NL problem
- PH = PSPACE problem
- L = P problem
- L = RL problem
- Unique games conjecture
- Is the exponential time hypothesis true?
- Is the strong exponential time hypothesis (SETH) true?
- Do one-way functions exist?
- Is public-key cryptography possible?
- Log-rank conjecture
- Hartmanis–Stearns conjecture
Polynomial versus nondeterministic-polynomial time for specific algorithmic problems
- Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
- Can the discrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
- Can the shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
- Can the graph isomorphism problem be solved in polynomial time on a classical computer?
The graph isomorphism problem involves determining whether two finite graphs are isomorphic, meaning there is a one-to-one correspondence between their vertices and edges that preserves adjacency. While the problem is known to be in NP, it is not known whether it is NP-complete or solvable in polynomial time. This uncertainty places it in a unique complexity class, making it a significant open problem in computer science.[2]
- Is graph canonization polynomial-time equivalent to the graph isomorphism problem?
- Can leaf powers and k-leaf powers be recognized in polynomial time?
- Can parity games be solved in polynomial time?
- Can the rotation distance between two binary trees be computed in polynomial time?
- Can graphs of bounded clique-width be recognized in polynomial time?[3]
- Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?[4]
- Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?[5]
- Can the square-root sum problem be solved in polynomial time in the Turing machine model?
Algorithmic number theory
- Skolem problem: Is it decidable whether an algebraic linear recurrence sequence has a zero?
- Hilbert’s tenth problem over the field of rational numbers
Other algorithmic problems
- The dynamic optimality conjecture: Do splay trees have a bounded competitive ratio?
- Can a depth-first search tree be constructed in NC?
- Can the fast Fourier transform be computed in o(n log n) time?
- What is the fastest algorithm for multiplication of two n-digit numbers?
- What is the lowest possible average-case time complexity of Shellsort with a deterministic fixed gap sequence?
- Can 3SUM be solved in strongly sub-quadratic time, that is, in time O(n2−ϵ) for some ϵ > 0?
- Can the edit distance between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.)
- Can X + Y sorting be done in o(n2 log n) time?
- What is the fastest algorithm for matrix multiplication?
- Can all-pairs shortest paths be computed in strongly sub-cubic time, that is, in time O(V3−ϵ) for some ϵ > 0?
- Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
- Does linear programming admit a strongly polynomial-time algorithm? (This is problem #9 in Smale’s list of problems.)
- How many queries are required for envy-free cake-cutting?
- What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST problem? The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown.
- Gilbert–Pollak conjecture: Is the Steiner ratio of the Euclidean plane equal to ?
Programming language theory
- Barendregt–Geuvers–Klop conjecture: Is every weakly normalizing pure type system also strongly normalizing?
Other problems
- Is multiplicative-exponential linear logic decidable?
- Is the Aanderaa–Karp–Rosenberg conjecture true?
- Černý conjecture: If a deterministic finite automaton with states has a synchronizing word, must it have one of length at most ?
- Generalized star-height problem: Can all regular languages be expressed using generalized regular expressions with a limited nesting depth of Kleene stars?
- Separating words problem: How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length ?
- What is the Turing completeness status of all unique elementary cellular automata?
- Determine whether the length of the minimal uncompletable word of is polynomial in , or even in . It is known that is a variable-length code if for all , implies and for all . In such cases, we do not yet know if a polynomial bound exists. This is a possible weakening of the Restivo conjecture (already disproven in general, though upper bounds remain unknown).
- Determine all positive integers such that the concatenation of and in base uses at most distinct characters, for fixed and .[citation needed]
Many other problems in coding theory are also listed among the unsolved problems in mathematics.
References
- “P vs. NP – The Greatest Unsolved Problem in Computer Science”. Quanta Magazine. 2023-12-01. Retrieved 2025-03-11.
- Klarreich, Erica (2015-12-14). “Landmark Algorithm Breaks 30-Year Impasse”. Quanta Magazine. Retrieved 2025-03-11.
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009). “Clique-width is NP-complete” (PDF). SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256. MR 2519936. S2CID 18055798. Archived from the original (PDF)on 2019-02-27.
- Demaine, Erik D.; O’Rourke, Joseph (2007). “24 Geodesics: Lyusternik–Schnirelmann”. Geometric folding algorithms: Linkages, origami, polyhedra. Cambridge: Cambridge University Press. pp. 372–375. doi:10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. MR 2354878.
- Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). “Simultaneous graph embeddings with fixed edges” (PDF). Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22–24, 2006, Revised Papers (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. ISBN 978-3-540-48381-6. MR 2290741.
External links
- Woeginger, Gerhard J. “Open problems around exact algorithms”. Discrete Applied Mathematics. 156 (2008), 397–405.
- The RTA list of open problems – Open problems in rewriting.
- The TLCA List of Open Problems – Open problems in the area of typed lambda calculus.
1,137,718 views 1 Dec 2023. Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science. This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions. Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog: https://scottaaronson.blog/ Read the companion article about meta-complexity at Quanta Magazine: https://www.quantamagazine.org/comple… 00:00 Introduction to the P vs NP problem 02:16 Intro to Computational Complexity 02:30 How do computers solve problems? 03:02 Alan Turing and Turing Machines 04:05 George Boole and Boolean Algebra 05:21 Claude Shannon and the invention of transistors 06:22 John Von Neumann and the invention of the Universal Electronic Computer 07:05 Algorithms and their limits 08:22 Discovery of different classes of computational problems 08:56 Polynomial P problems explained 09:56 Exponential NP Problems explained 11:36 Implications if P = NP 12:48 Discovery of NP Complete problems 13:45 Knapsack Problem and Traveling Salesman problem 14:24 Boolean Satisfiability Problem (SAT) defined 15:32 Circuit Complexity Theory 16:55 Natural Proofs Barrier 17:36 Meta-complexity 18:12 Minimum Circuit Size Problem (MCSP). VISIT our Website: https://www.quantamagazine.org