# Tagged Questions

**3**

votes

**0**answers

120 views

### Both NP-hard but different [on hold]

What's the fundamental difference between the Knapsack problem and the travelling salesman (TSP) problem both of which are NP-hard, while the reality is that TSP could be solved much much faster?

**3**

votes

**3**answers

730 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 ...

**1**

vote

**1**answer

35 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
$$ ...

**1**

vote

**0**answers

119 views

### Basis of periodic tiling of Wang tile

Given a set of Wang tile,
Given 3 periodic tiling: A, B, C
We define 3 vector F[A], F[B], F[C]
each vector correspond to the appearing frequency of each type of tiles in the tiling.
Now, we ...

**2**

votes

**1**answer

97 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 ...

**2**

votes

**0**answers

101 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 ...

**4**

votes

**1**answer

345 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 ...

**4**

votes

**2**answers

186 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 ...

**6**

votes

**6**answers

632 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 ...

**2**

votes

**0**answers

92 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 ...

**24**

votes

**10**answers

2k 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$ ...

**4**

votes

**0**answers

223 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 ...

**3**

votes

**2**answers

258 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 ...

**10**

votes

**2**answers

351 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**

vote

**3**answers

140 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 ...

**2**

votes

**1**answer

112 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 ...

**2**

votes

**1**answer

293 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)$ ...

**4**

votes

**3**answers

365 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$, ...

**4**

votes

**1**answer

101 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 ...

**23**

votes

**1**answer

675 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
...

**1**

vote

**1**answer

152 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 http://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here.
In ...

**2**

votes

**2**answers

128 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 ...

**16**

votes

**1**answer

552 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 ...

**3**

votes

**2**answers

96 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 ...

**6**

votes

**3**answers

590 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 ...

**3**

votes

**1**answer

249 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 ...

**4**

votes

**1**answer

443 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
...

**10**

votes

**2**answers

483 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 ...

**12**

votes

**1**answer

572 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 ...

**9**

votes

**1**answer

1k 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. ...

**6**

votes

**1**answer

236 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 ...

**5**

votes

**2**answers

458 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 ...

**1**

vote

**0**answers

166 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 $M$ accepting
$$
\text{coBHP}=\{\langle ...

**9**

votes

**2**answers

1k 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 ...

**9**

votes

**4**answers

2k 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 ...

**1**

vote

**0**answers

1k views

### Quantum computation implications of (P vs NP) [duplicate]

Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?
Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that ...

**11**

votes

**2**answers

2k 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 ...

**7**

votes

**3**answers

1k 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 ...

**14**

votes

**2**answers

1k 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 ...

**2**

votes

**7**answers

931 views

### Completeness, easiest, hardest problems

One says that a language $L$ is complete for a complexity class $\mathcal{C}$ if $L$ is in $\mathcal{C}$ and every language in $\mathcal{C}$ is reducible to $L$. Thus, in a sense, $L$ is the hardest ...

**23**

votes

**2**answers

1k 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$, ...

**16**

votes

**5**answers

3k 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 ...

**19**

votes

**3**answers

2k 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 ...

**1**

vote

**4**answers

2k views

### A subset of all languages which is uncountable?

Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all ...