# Tagged Questions

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

**23**

votes

**1**answer

684 views

### How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$.
Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My ...

**1**

vote

**2**answers

232 views

### Computational complexity of solution of Pell equation and more

What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?
And more,could ...

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

**7**

votes

**1**answer

162 views

### What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?

Questions:
Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation ...

**4**

votes

**1**answer

108 views

### Kolmogorov complexity of at least one string (from amongst those of a given length) is equal to its length

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ?(For any alphabet with more than 1 symbol)
Is there a proof if the answer is in ...

**4**

votes

**2**answers

213 views

### Cubic graphs decompositions

There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor ...

**1**

vote

**0**answers

93 views

### Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
...

**2**

votes

**0**answers

108 views

### Reference Request: Properties of the Integer Factorization Polytope

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online ...

**4**

votes

**0**answers

75 views

### Can the isomorphism relation for countable models become harder when adding finitely many constants?

I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property.
Context: view the ...

**8**

votes

**1**answer

206 views

### Fold-and-cut problem in three dimensions

The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...

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

**5**

votes

**0**answers

116 views

### Computational complexity of resolution of singularities of varieties over fields with characteristic 0 [closed]

What is the computational complexity of resolution of singularities of varieties over fields with characteristics 0?

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

**6**

votes

**1**answer

318 views

### compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...

**4**

votes

**1**answer

670 views

### Turing machines that always halt

Needed for this paper:
Here is a possibly more clear version of my question. A Turing machine (with $1$ tape) has sets of tape letters $Y$, state letters $Q$, two symbols $\alpha$ and $\omega$ that ...

**2**

votes

**0**answers

335 views

### Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of ...

**4**

votes

**2**answers

1k views

### the complexity of Lanczos method

Hi, all
I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of ...

**2**

votes

**1**answer

180 views

### Survey on Structural Complexity

Alot of the proofs I've been recently reading:
IP / PSpace / MIP / NEXP / randomized reductions
have a certain flavour involving proofs showing equivalence/relation between various complexity ...

**9**

votes

**2**answers

307 views

### Do there exist groups with word problems in arbitrary P-degrees?

This has been posted on TCS stack exchange for a while here and hasn't gotten any answers, so I'm trying again here.
It has been known for a long time that, given any r.e. Turing degree, there is a ...

**2**

votes

**0**answers

268 views

### Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...

**5**

votes

**0**answers

503 views

### Is integer factorization harder than RSA ($n=pq$) factorization? [closed]

This is a repost. I could not get a precise answer on math.SE and cstheory.SE
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers ...

**1**

vote

**0**answers

262 views

### Complexity of a problem related to 3D matching?

Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D ...

**24**

votes

**4**answers

1k views

### Algebraic P vs. NP

I recently attended a lecture where the speaker mentioned that what he was talking about was connected to the algebraic version of the $P$ vs. $NP$ problem. Could someone explain what that means in a ...

**3**

votes

**1**answer

201 views

### Theorems about the directed bandwidth of a rooted tree?

Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...

**1**

vote

**3**answers

228 views

### Where does the game-theoretic characterization of PH come from?

I have read in a few places that $\mathbf{PH}$ can be interpreted in terms of the complexity of determining the winner in two-player games. I would like to know a) the original reference for this ...

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

**31**

votes

**9**answers

3k views

### What is the shortest program for which halting is unknown?

In short, my question is:
What is the shortest computer program for which it is not known whether or not the program halts?
Of course, this depends on the description language; I also have the ...

**0**

votes

**1**answer

114 views

### A result about LSpace and RLSpace

I heard that there is a result which is proved that RL\subseteq L^{4/3}, but I don't which paper have proved it.
Can someone tell me this paper?

**0**

votes

**1**answer

391 views

### cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]

Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that ...