# Tagged Questions

**42**

votes

**2**answers

6k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly Orthogonal to Morse
!
Harold Calvin Marston Morse (24 March ...

**28**

votes

**7**answers

3k views

### Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...

**6**

votes

**2**answers

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

**16**

votes

**2**answers

1k views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...

**30**

votes

**1**answer

1k views

### How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...

**15**

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

**13**

votes

**6**answers

1k views

### SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...

**7**

votes

**2**answers

700 views

### Building a Physical Model to Solve Sudoku

Before asking my questions, allow me to begin with a separate example to help clarify what I'm driving at. For terms that are not defined formally, please interpret them as you feel would be most ...

**7**

votes

**2**answers

1k views

### Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...

**5**

votes

**2**answers

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

**4**

votes

**1**answer

287 views

### an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.
I mean there is polynomial reduction $F$ such that for every boolean ...

**1**

vote

**1**answer

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

**12**

votes

**5**answers

1k views

### Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$

Found this on Complexity Zoo warning expired certificate
check NP Over The Complex Numbers.
[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum ...

**32**

votes

**7**answers

17k views

### Example of a good Zero Knowledge Proof.

I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...

**21**

votes

**3**answers

2k views

### Discrete Fourier Transform of the Möbius Function

Consider the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Next consider for some natural number ...

**20**

votes

**2**answers

2k views

### Simulating Turing machines with {O,P}DEs.

Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao:
For instance, one cannot hope to find an algorithm to determine the existence of ...

**26**

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

**16**

votes

**1**answer

3k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**37**

votes

**6**answers

3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**17**

votes

**4**answers

2k views

### Complexity of testing integer square-freeness

How fast can an algorithm tell if an integer is square-free?
I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH ...

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

**20**

votes

**2**answers

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

**17**

votes

**4**answers

923 views

### Complexity of equitable partitions

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...

**16**

votes

**6**answers

5k views

### Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...

**6**

votes

**2**answers

3k views

### Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...

**19**

votes

**3**answers

1k views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**17**

votes

**1**answer

2k views

### Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows.
Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...

**14**

votes

**1**answer

775 views

### Who first dubbed them “expander graphs”?

Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the ...

**7**

votes

**3**answers

1k views

### Grover's Quantum Search Algorithm

I am confused about an extremely basic point concerning Grover's quantum search algorithm; my confusion suggests to me that maybe I've missed the entire point.
My understanding of the algorithm is ...

**6**

votes

**2**answers

507 views

### Computational complexity of the word problem for semi-Thue systems with certain restrictions

The word problem (from wikipedia).
Given a semi-Thue system T: = (Σ,R)
and two words , can u be transformed
into v by applying rules from R?
This problem is undecidable, but with a certain ...

**5**

votes

**2**answers

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

**17**

votes

**4**answers

687 views

### Enumeration and random selection

In Peter J. Cameron's book "Permutation Groups" I found the following quote
It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a ...

**7**

votes

**1**answer

489 views

### Can we invert barycentric subdivision?

With apologies to fellow algebraic topologists, I confess that I have no idea how to answer this innocent-looking question:
(1) Let's say we know that a finite simplicial complex $S$ is the ...

**6**

votes

**2**answers

2k views

### Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...

**5**

votes

**6**answers

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

**4**

votes

**2**answers

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

**1**

vote

**2**answers

157 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**16**

votes

**1**answer

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

**7**

votes

**1**answer

444 views

### Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?

**5**

votes

**1**answer

157 views

### Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...

**3**

votes

**1**answer

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

**2**

votes

**3**answers

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

**12**

votes

**2**answers

202 views

### Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...

**10**

votes

**2**answers

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

**6**

votes

**1**answer

1k views

### Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value

Setup
Let $A$ be a stochastic matrix.
Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$.
Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$
Question:
...

**5**

votes

**0**answers

217 views

### Is there a program for theory of incompleteness in NP?

Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for ...

**5**

votes

**1**answer

442 views

### Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418

I am not familiar with newforms, so this may not make any sense.
OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3]
Numerical evidence suggest that up to $10^5$
$$ ...

**4**

votes

**1**answer

126 views

### Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula:
$$\phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right ...

**4**

votes

**1**answer

87 views

### The link and equivalence between variant definition of computation model and computational complexity over reals

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...

**4**

votes

**3**answers

339 views

### powers in strings

I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th ...