All Questions
10 questions with no upvoted or accepted answers
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 ...
- 20.5k
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 ...
- 20.5k
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
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
4
votes
0
answers
568
views
About "natural proof" of Razborov and Rudich
The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
- 781
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
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
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
2
votes
0
answers
163
views
Graph theoretical representation of Wang Tile
We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...
- 867