All Questions
Tagged with computability-theory computational-complexity
111 questions
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
2
votes
1
answer
287
views
Effectively non-recursiveness of some sets
A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$. A set is effectively non-recursive if it is r.e. and its ...
- 870
1
vote
0
answers
203
views
A reference for "Borel Sets and Circuit Complexity"
Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?
- 51
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
273
views
Analogue break down between complexity theory and computability theory
Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving ...
- 2,993
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
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
4
votes
1
answer
220
views
The link and equivalence between variant definition of computation model and computational complexity over reals
To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...
- 3,094
1
vote
1
answer
202
views
The definition of computational complexity or complexity measure of computing reals [closed]
A real $r$ is computable if given any $i\in \mathbb{N}$, the $i$th bit can be outputed by a Turing Machine or an algorithm. So, what is computational complexity or complexity measure of computing the ...
- 3,094
1
vote
1
answer
243
views
A possible minimal aperiodic set of corner Wang Tile
From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...
- 867
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
2
votes
3
answers
476
views
How to define the input of computable function or Turing machine over real numbers
Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
- 3,094
2
votes
3
answers
987
views
An established proof in Wang Tile which I doubt
When I was reading the paper:
Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305.
from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf
I could not ...
- 867
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
1
vote
1
answer
631
views
relationship between corner tile and edge tile of wang tile
It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...
- 867
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
3
votes
1
answer
509
views
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
- 867
3
votes
2
answers
297
views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
- 867
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
2
votes
0
answers
123
views
What are natural examples of non-relativizable proofs? [duplicate]
As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).
Virtually all proofs seem to be relativizable, though.
What are good examples of ...
- 179
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
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 ...
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
4
votes
1
answer
358
views
$\mu$-recursive definitions for the complexity classes P, NP, etc
The standard complexity classes such as P, NP are usually defined using Turing Machines. In finite model theory those classes can be defined via the classical first-order/second-order logics.
I am ...
- 43
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
4
votes
1
answer
158
views
About infinite subset of halting probability and 1-random set
Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is ...
- 3,038
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)=\...
1
vote
1
answer
292
views
Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?
I failed to get an answer at https://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here.
In https://math....
- 11
2
votes
2
answers
166
views
Size-limited oracles
I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:
Suppose that an invocation of an algorithm f with an input of size n has access to an oracle ...
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
3
votes
2
answers
162
views
How would one characterize a PR-complete language?
The complexity class $PR$ is the set of all formal languages that can be decided by a primitive recursive function. Is there any language $l$ known to be complete for this class, i.e., for every ...
- 283
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
3
votes
1
answer
445
views
Diagonalization and classes of computable functions
Fix a standard effective listing $(\phi_e)_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow \...
- 21.2k
4
votes
1
answer
830
views
Infinite monkeys computing ... triangle area?
I wonder if it is possible to specialize the question:
(a) What is the probability that a random Turing Machine program
will halt?, to: (b) What is the probability that a random Turing Machine
...
- 151k
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
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
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
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
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
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
3
votes
1
answer
266
views
A question about the "information-content" of a very simple type of Turing machine.
All the Turing machines we consider have (1) a two-way infinite tape (2) one and only one halting
state (3) an alphabet of exactly two symbols-"1" and " "(or "blank"). Let n be any positive integer.
...
- 6,215
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 ...
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
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}=\{\...
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