All Questions
26 questions
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
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
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
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
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
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
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}$ ?...
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
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
2
votes
2
answers
624
views
Time Hierarchy Theorem and P vs NP
One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
- 99
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
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 ...
1
vote
1
answer
280
views
How to select a subset of points from a universal to minimize the distance from outside to inside?
Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ d(...
- 573
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
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
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
1
vote
3
answers
693
views
unbounded complexity
If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting ...
- 11
1
vote
1
answer
324
views
Problem to a solution
Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
- 11
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
3
votes
1
answer
386
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 77
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
4
votes
1
answer
248
views
Constructing hard inputs for the complement of bounded halting
If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
\text{coBHP}=\{\...
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