computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

28
votes
7answers
2k 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
2answers
554 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
2answers
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 ...
41
votes
2answers
5k 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 ...
29
votes
1answer
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
4answers
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 ...
7
votes
2answers
695 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
2answers
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 ...
1
vote
1answer
240 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
5answers
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 ...
30
votes
7answers
15k 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
3answers
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 ...
16
votes
1answer
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 ...
13
votes
6answers
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 ...
35
votes
6answers
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 ...
23
votes
2answers
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
2answers
934 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 ...
15
votes
4answers
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 ...
15
votes
6answers
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 ...
15
votes
4answers
857 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 ...
6
votes
2answers
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: ...
17
votes
1answer
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 ...
15
votes
2answers
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 ...
13
votes
1answer
752 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
3answers
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
2answers
500 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
2answers
317 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
4answers
680 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 ...
6
votes
2answers
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
6answers
864 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
2answers
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
2answers
155 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
1answer
694 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
1answer
435 views

Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
5
votes
1answer
150 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 ...
5
votes
2answers
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 ...
3
votes
1answer
416 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
3answers
790 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 ...
10
votes
2answers
506 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
1answer
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
1answer
441 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
0answers
208 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 ...
4
votes
1answer
83 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
3answers
338 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 ...
4
votes
3answers
259 views

Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$. Given $g$ and either $$ A = x g^ x$$ or $$ A = x g^{x^2-1}$$ find $x$. What is the complexity of solving this? Is there a reduction to the discrete ...
4
votes
2answers
525 views

Simplified knapsack problem

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
4
votes
2answers
375 views

Sets of vectors related by a rotation

We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$. The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ ...
4
votes
2answers
1k views

What is the probability a random Turing machine is isomorphic to a DFA?

This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the ...
3
votes
0answers
163 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
3
votes
1answer
110 views

Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In Theorem 2 On the second page it states there exists ...