# Tagged Questions

**3**

votes

**3**answers

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

**3**

votes

**0**answers

119 views

### characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...

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

86 views

### simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...

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

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

**6**

votes

**0**answers

166 views

### When is a reduction not a reduction?

Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of ...

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

**10**

votes

**1**answer

279 views

### Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$

Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free.
In them he ...

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

**17**

votes

**2**answers

789 views

### Deep theorems and long proofs

I ran across this discussion by Daniel Shanks,
"Is the quadratic reciprocity law a deep theorem?."
Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff.
which made me ...

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

**5**

votes

**0**answers

148 views

### Feasible Type Theories

I am looking for references about efficient type theories,
efficiency in the sense of computational complexity,
and type theory in the sense of Martin-Lof's type theories.
Has there been any studies ...

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

**6**

votes

**1**answer

410 views

### Normality of Chaitin's constant

Can anyone provide an overview of the proof that Chaitin's constant is normal, or better yet, the guiding intuition?
Even if we replace the existential quantifiers in the assertion of non-normality ...

**1**

vote

**1**answer

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

**16**

votes

**1**answer

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

**9**

votes

**6**answers

1k views

### Non-constructive proofs vs. efficient algorithms

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...

**13**

votes

**1**answer

586 views

### Forcing over set theory versus forcing over arithmetic

I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...

**6**

votes

**3**answers

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

**14**

votes

**4**answers

3k views

### What would be some major consequences of the inconsistency of ZFC?

I was happily surfing the arXiv, when I was jolted by the following paper:
Inconsistency of the Zermelo-Fraenkel set theory with the axiom of choice and its effects on the computational complexity by ...

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

**3**

votes

**1**answer

217 views

### Is $MIN^P$ search problem (partial order) reducible to $MIN^L$ (linear order) search problem?

Search problem $MIN^P$ is, given a polynomial-time computable predicate that is a partial order, to find its minimum (any will do).
Search problem $MIN^L$ is, given a polynomial-time computable ...

**3**

votes

**2**answers

517 views

### Measure of progress towards a proof

Can one define some measure of progress towards a proof of a statement? I'm not sure if it's even possible for general first order logic statements so let's restrict ourselves to propositional ...

**7**

votes

**2**answers

857 views

### Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...

**7**

votes

**3**answers

660 views

### Definition of relativization of complexity class

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?
Usually, these classes and their relativizations seem to be defined in an ad-hoc ...

**2**

votes

**1**answer

452 views

### How much of P versus NP's difficulty stems from having to rule out the existence of Turing machines that “accidentally” solve, say, 3-SAT efficiently?

It seems like there is a sense in which a Turing machine that demonstrates P=NP could be said to "accidentally" exist. I'm wondering the extent to which the possibility of such machines is the main ...

**3**

votes

**1**answer

460 views

### Proof systems and their hierarchy

Why ZFC is placed in top of the proof system hierarchy? How it can p-simulate other systems?

**27**

votes

**2**answers

1k views

### The NP version of Matiyasevich's theorem

By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has ...

**2**

votes

**0**answers

194 views

### Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)

Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an ...

**2**

votes

**2**answers

532 views

### Natural numbers of great kolmogorov complexity

Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...

**2**

votes

**2**answers

1k views

### Do you believe P=NP? [closed]

Do you believe P=NP?
I've seen some mathematicians say that if P=NP their work would be worthless and restricted to enunciating theorems. They seem to believe that there exist an almost philosophical ...

**8**

votes

**5**answers

414 views

### Syntactically capturing complexity classes

Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...

**5**

votes

**4**answers

1k views

### Zero-knowledge proof that 0 = 1

Suppose one day I came up with a proof that 0 = 1 in some formal system such as PA or ZFC that cannot prove its own consistency (unless it is inconsistent). Would it be possible to have a ...

**25**

votes

**8**answers

2k views

### Is P=NP relevant to finding proofs of everyday mathematical propositions?

Disclaimer: I don't know a whole lot about complexity theory beyond, say, a good undergrad class.
With increasing frequency I seem to be encountering claims by complexity theorists that, in the ...

**13**

votes

**2**answers

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

**11**

votes

**2**answers

716 views

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...

**6**

votes

**2**answers

1k views

### Horn clauses and satisfiability

It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation.
But suppose we relax the condition for horn clauses from at most one un-negated ...

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

**3**

votes

**0**answers

272 views

### To what extent MSO = WS1S, when adding relations?

Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...

**3**

votes

**4**answers

446 views

### Deriving the complete set of “non-redundant” true statements in disjunctive form in propositional logic

Given a finite set of statements known to be true, I need to derive all the "non-redundant" statements in disjunctive form using only literals that can be derived from this set of statements, i e all ...

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