# Tagged Questions

**13**

votes

**2**answers

352 views

### What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$

Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...

**6**

votes

**0**answers

316 views

### Any reason to believe that $NP \neq P$ is unprovable in ZFC

We know $NP \neq P$ from a lot of point of view like empirical reason,or theoretical reasons such as finite model theory or descriptive complexity.Although we find so many reasons to believe $NP \neq ...

**1**

vote

**1**answer

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

**2**

votes

**3**answers

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

**2**

votes

**3**answers

740 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

749 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

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

**1**

vote

**0**answers

104 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

164 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

112 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

224 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

107 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

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

**5**

votes

**0**answers

85 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

217 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

158 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

122 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

447 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

321 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

679 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

339 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

309 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

274 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

509 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

202 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

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

**32**

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?

**-1**

votes

**1**answer

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