# Tagged Questions

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

120 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

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

**66**

votes

**9**answers

7k views

### Analogues of P vs. NP in the history of mathematics

Recently I wrote a blog post entitled "The Scientific Case for P≠NP". The argument I tried to articulate there is that there seems to be an "invisible electric fence" separating the problems in P ...

**3**

votes

**1**answer

181 views

### Class Separation, Oracles, Relativization

It is known, there exists oracles A, B s.t.:
$P^A = NP^A; P^B \neq NP^B$, showing that any proof of P vs NP must be non-relativizing.
Questions:
(1) Can we actually use Oracles to separate ...

**4**

votes

**1**answer

267 views

### Interesting complexity classes $PR \subsetneq c \subsetneq R$

I'm working on a proof-checker that can verify termination proofs. The fundamental method it provides for constructing such proofs is to translate the program into primitive recursion. Basically, I ...

**11**

votes

**7**answers

2k views

### Most 'obvious' open problems in complexity theory

What open problems in computational complexity theory have the most 'obvious' answers, regardless of whether that answer is true or false? The problems I'm talking about certainly have more 'obvious' ...

**5**

votes

**3**answers

1k views

### When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$? [closed]

From time to time, people announce papers claiming to have settled long open problems like $P$ vs. $NP$. There have been many attempts, reading them is time-consuming, and finding bugs in their ...

**2**

votes

**1**answer

699 views

### Probability of system failure in a distributed network

I am trying to build a mathematical model of the availability of a file in a distributed file-system. The system works like this: a node $x$ stores a file $f$ (encoed using erasure codes) at $rb$ ...

**4**

votes

**5**answers

690 views

### Quantum Computing Complexity?

After reading a recent post on Church's Thesis, I ran into Turing-Church's Strong Thesis, that may be potentially disproven by advances in Quantum Computing. Does anyone know of a good resource that ...