All Questions
Tagged with computability-theory computational-complexity
111 questions
113
votes
11
answers
18k
views
On mathematical arguments against Quantum computing
Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
31
votes
3
answers
3k
views
Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...
- 236k
29
votes
3
answers
3k
views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
29
votes
2
answers
1k
views
Determining if a rational function has a subtraction-free expression
This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
- 2,753
27
votes
10
answers
4k
views
Can We Decide Whether Small Computer Programs Halt?
The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...
- 711
26
votes
6
answers
9k
views
The problem of finding the first digit in Graham's number
Motivation
In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
- 1,593
24
votes
1
answer
1k
views
Are sums of sequences decidable?
Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
$\sum_{n=0}^{\infty}f(n)=\...
22
votes
5
answers
5k
views
Why relativization can't solve NP !=P?
If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...
- 581
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
18
votes
1
answer
1k
views
Is it possible to make an algorithm that could predict the likelihood that a program will halt?
Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
- 313
18
votes
2
answers
1k
views
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy
to test for membership but a lot more difficult to find members, and for others
the reverse is true. Here is an elementary ...
- 15.3k
17
votes
4
answers
3k
views
Languages beyond enumerable
A language is a set of finite-length strings from some finite alphabet $\Sigma$.
It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings.
...
- 151k
17
votes
1
answer
960
views
Polynomial-time algorithm to compare numbers in Conway chained arrow notation
I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
- 171
16
votes
2
answers
2k
views
Structure theorems for Turing-decidable languages?
Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...
- 23k
15
votes
2
answers
2k
views
How did the Baker-Gill-Solovay paper come to be?
How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
user44143
15
votes
1
answer
1k
views
Is there a known primitive recursive upper bound on the nth "Zhang prime"
(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
- 6,287
15
votes
0
answers
425
views
Complexity classes for BSS machines
Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...
- 21.2k
14
votes
1
answer
4k
views
Kolmogorov Complexity and Proof Techniques
I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity.
Definition:(Sipser) Let x be a binary string. ...
- 243
13
votes
6
answers
3k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
13
votes
3
answers
834
views
Undecidable infinite analogs of NP-complete problems?
In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
13
votes
2
answers
1k
views
What is known in general about the liquid transfer problem?
In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
- 2,075
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
- 2,576
13
votes
1
answer
973
views
Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?
It is well known that every partial order on a set can be extended
to a linear order on that set. That is, for every partial order
$\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such
that ...
- 236k
12
votes
2
answers
3k
views
Is the solution bounded Diophantine problem NP-complete?
Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given ...
- 2,791
12
votes
2
answers
2k
views
What is the probability a random Turing machine is isomorphic to a DFA?
This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the ...
- 2,392
12
votes
2
answers
3k
views
What impact would P!=NP have on the characterization of BQP?
Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
- 267
12
votes
4
answers
4k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 3,897
11
votes
2
answers
668
views
What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?
Disjoint sets $A$ and $B$ are computably inseparable, if there
is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The
existence of c.e. computably inseparable ...
- 236k
11
votes
2
answers
964
views
What Turing-Complete models of computation carry a notion of time complexity that "agrees" with that of Turing Machines?
Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...
- 1,389
10
votes
1
answer
396
views
Groups whose word problem can be solved in constant time
Given a finitely generated group $G$, define an encoding of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, ...
- 799
9
votes
2
answers
954
views
What theories are larger than the real closed field but still decidable?
It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
- 2,689
9
votes
1
answer
372
views
Decidable theories with arbitrary complexity
Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity?
Here, arbitrarily high (computational) complexity means that for every ...
- 7,545
7
votes
3
answers
2k
views
Decidable but nonrecursive sets
Until recently, I believed that recursive=decidable,
subscribing to this Wikipedia quote:
"In computability theory, a set is decidable, computable, or recursive if there
is an algorithm that ...
- 151k
7
votes
2
answers
1k
views
Complexity of Turing Machine behavior
If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}...
- 151k
7
votes
1
answer
258
views
Oracle queries asked in parallel
Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
6
votes
3
answers
1k
views
computational complexity of primitive recursive functions
If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
- 63
6
votes
3
answers
961
views
What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
Let me begin with an example.
Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
- 693
6
votes
2
answers
908
views
A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size
I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...
- 81
6
votes
2
answers
276
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,029
6
votes
1
answer
357
views
computing abelianizations
Suppose I have a finitely presented group $G,$ and a subgroup $H$ of $G$ given by its finite generating set (given as words in the generators of $G.$ I want to know whether $H/[H, H]$ is finite. Is ...
- 96.4k
6
votes
2
answers
308
views
Recent trends in effective analysis
The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...
user60665
6
votes
1
answer
1k
views
MIP^*=RE and quantum computation
I recently learned about the MIP^*=RE result. I have to admit that I don't understand big parts of this paper and I am barely familiar with quantum physics. I hope my questions below make sense.
I ...
- 2,882
6
votes
1
answer
216
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
user39297
6
votes
1
answer
214
views
Finite-variable fragments of $\Delta_0$-formulas
Consider sets definable in the usual structure of arithmetic $(\mathbb{N},0,1,+,\times)$ by $\Delta_0$-formulas, i.e., formulas with bounded quantifiers. The quantifier alternation hierarchy has been ...
- 211
5
votes
6
answers
2k
views
practical algorithms for np complete problems
Inspired by:
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
And the practicality of this topic (solving tessellation on a lattice):
coloring in lattice
Computational ...
- 867
5
votes
3
answers
1k
views
Is There An Algorithmic Complexity Of A Random Distribution
Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
5
votes
1
answer
345
views
Decoding a Remark of Gödel on Complexity Theory
In Gödel's Collected Works (Vol 2), there is a discussion of von Neumann which was brought about by a query, made to Gödel, concerning the existence of a Turing machine which is so complex that its ...
- 314
5
votes
1
answer
213
views
Aperiodic set of corner Wang Tile [closed]
There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
- 867
5
votes
0
answers
192
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
- 3,029
5
votes
0
answers
246
views
Does $\mathsf{Q}$ have any interesting provably recursive functions?
This question was asked and bountied at MSE without success.
For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...
- 21.2k