All Questions
Tagged with computability-theory computational-complexity
111 questions
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
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,094
3
votes
1
answer
308
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
- 81
4
votes
0
answers
214
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
- 81
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
1
vote
0
answers
116
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
- 9,330
1
vote
1
answer
98
views
How large can a subset of computable reals, whose comparison function is computable, grow?
How large can a subset of computable reals, whose comparison function is computable, grow?
For example, rational numbers are computable reals, and its comparison function is computable. As another ...
- 325
1
vote
0
answers
67
views
Are the lower elementary functions closed under limited recursion?
The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
- 1,782
2
votes
1
answer
125
views
The counterpart of productive set with polynomial computational complexity
For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
- 3,094
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
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
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 "...
3
votes
0
answers
186
views
Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$
Suppose we have two computable functions $f, g:\mathbb{N}\to\mathbb{N}$. When is $f=g$ algorithmically decidable?
For example it is decidable if $f$ and $g$ are polynomials of a priori known degree.
- 31
0
votes
1
answer
267
views
Algorithmically decide if an algorithm has optimal time complexity [closed]
Is there an algorithm with the following input and output?
INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs.
OUTPUT: "YES"...
- 1
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
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
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
0
votes
0
answers
56
views
Reference about Relation between Probabilistic Turing Machine and Turing Machine of every hierarchy
What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?...
- 3,094
5
votes
0
answers
301
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
- 3,871
1
vote
0
answers
127
views
Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level
Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
- 3,094
0
votes
1
answer
118
views
Are all $P$-noncomputable sets $P$-random? [duplicate]
$P$ means polynomial complexity.
$S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example?
what is the ...
- 3,094
3
votes
1
answer
293
views
Relationship between P-noncomputable and P-random sets
$P$ means polynomial complexity.
$S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ noncomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...
- 3,094
2
votes
0
answers
404
views
Halting problem for bounded length programs
Consider a set $M_n$ of all Turing machines with at most $n$ states. What is the smallest number of states (asymptotically in $n$) a Turing machine must have in order to solve halting problems for all ...
- 1,251
2
votes
0
answers
103
views
Buridan's principle in computable analysis
In (Lamport, 2012), Lamport proposes the principle
A discrete decision based upon an input
having a continuous range of values cannot be made within a bounded length of time.
I think it could be ...
3
votes
1
answer
767
views
does recursive (decidable) languages closed under division (Quotient) with any language?
I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...
- 51
3
votes
2
answers
331
views
Time functions of non-deterministic Turing machines (a better question)
This is a more precise version of that question.
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation ...
user6976
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 ...
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
2
votes
0
answers
148
views
what is the relationship between the complexity of a function and the complexity of it's graph set?
Given $f: \omega \rightarrow \omega$ , what is the relationship between the following two notions:
(i) the computational complexity of f (in the standard sense, say with naturals represented in ...
- 21
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
5
votes
0
answers
106
views
Collapsing the Exponential time Hierarchy with a complete language as oracle
It is known that $\mathsf{P^A=NP^A}$ is true for every $\mathsf{EXP}$ complete language $\mathsf{A}$. The question is the whether the similar things hold for Exponential time Hierarchy.
Is there ...
- 1,689
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}$ ?...
1
vote
1
answer
308
views
Halting problem about subclass of Turing Machines
As we know, that the halting problem of Turing machines is undecidable. given some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can ...
- 3,094
2
votes
0
answers
90
views
Recursion theoretical Characterization of time complexity classes
Is there any known Recursion theoretical Characterization of time complexity classes like $\mathsf{DTIME(n^k)}$ or $\mathsf{NTIME(n^k)}$ for some fixed $k$?
Thanks.
- 1,689
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
-2
votes
1
answer
169
views
If the set of the output of a computable function is finite, is the sequence periodic eventually? [closed]
$$f:N \rightarrow B,\space B\subset N $$ and $B$ is finite, $S$ is the sequence constructed by $f(1),f(2)\cdots f(i)\cdots $.
Now, if $f$ is a computable function,is $S$ eventually periodic?
Update: ...
- 3,094
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
4
votes
2
answers
155
views
Are there complexity classes X weaker than the linear time hierarchy such that any r.e. set is a coordinate projection of a set in X?
If $A\subseteq\mathbb{N}$ is recursively enumerable, then there is a $\Delta^0_0$ set $B\subseteq\mathbb{N}^2$ such that $A=\{x|\exists y\;(x,y)\in B\}$. $\Delta^0_0$ consists of exactly the sets in ...
- 2,130
1
vote
1
answer
183
views
Understanding the paper: "Guarded Fixed Point Logic"
This question is specifically about the paper "Guarded Fixed Point Logic" by Gradel and Walukiewicz. Among other things they prove the decidability of the satisfiability problem for Fixpoint Loosely ...
- 111
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
1
vote
0
answers
152
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
- 2,576
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
1
vote
0
answers
129
views
Analogues of Specker sequences for different complexity classes
Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
- 1,155
0
votes
1
answer
3k
views
Turing and Many one reductions in computability versus complexity
What are some non-trivial (please exclude poly time definitional difference) differences between Turing versus Many-one reductions in computability theory and those that occur in complexity theory?
- 13.9k
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
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
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