Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

Filter by
Sorted by
Tagged with
40
votes
8answers
4k 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 ...
18
votes
2answers
967 views

Explicit invariant of tensors nonvanishing on the diagonal

The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
50
votes
2answers
7k 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 ...
21
votes
2answers
1k 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 ...
16
votes
2answers
2k 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 $...
6
votes
2answers
702 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
6answers
2k 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 ...
43
votes
6answers
4k 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 ...
34
votes
1answer
2k 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 ...
24
votes
7answers
7k 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 ...
14
votes
3answers
4k views

What are the current breakthroughs of Geometric Complexity Theory?

I've read from Wikipedia about Geometric Complexity Theory (GCT) which (if I understood correctly) is a program for coping with the $ P=NP $ problem using algebraic methods. That program seems ...
7
votes
2answers
764 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 ...
24
votes
2answers
841 views

Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
17
votes
1answer
1k views

Forcing over set theory versus forcing over arithmetic

I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...
7
votes
2answers
2k 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
1answer
2k views

Complexity for solving linear equations?

What is the best known complexity for finding a vector $x \in \mathbb{R}^n$ to minimize $||Ax - b||^2$ and/or to solve (when possible) the system of linear equations $Ax=b$? I am interested in ...
12
votes
1answer
458 views

Seeking references for finding primes infinitely often

I've been pondering this weakened version of the finding primes problem for a while: Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$? This differs from ...
5
votes
1answer
358 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 ...
5
votes
1answer
1k views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
3
votes
1answer
247 views

Relationship between P-noncomputable and P-random sets

$P$ means polynomial complexity. $S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ incomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example? what is ...
1
vote
1answer
491 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 ...
11
votes
3answers
400 views

Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism is NP-hard or harder? Graphs and groups are not solutions. Searching the web didn't return answer for me. Partial result based on Chow's ...
6
votes
1answer
861 views

Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
6
votes
1answer
270 views

Time functions of non-deterministic Turing machines

Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...
103
votes
11answers
14k views

On mathematical arguments against Quantum computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
43
votes
7answers
7k views

What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference? Long version of the question: I'm sort of surprised to be asking this, because ...
22
votes
5answers
8k views

Can all convex optimization problems be solved in polynomial time using interior-point algorithms?

Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
23
votes
3answers
3k 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 $...
30
votes
1answer
546 views

Guess that group via product queries

Suppose someone (person B) knows a finite group $G$ of order $n$. You (person A) know only the order $n$, and that $1$ is the name of the identity element. The group elements are named $1,2,\ldots,n$ ...
22
votes
4answers
4k views

Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
23
votes
1answer
5k 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 ...
18
votes
2answers
2k views

Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis. Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
12
votes
2answers
2k views

Connections between Complexity Theory & Set Theory

Inspired by Joshua Grochow and Iddo Tzameret's answers in a post on http://cstheory.stackexchange.com , I would like to get more references on possible connections between complexity theory and set ...
25
votes
0answers
1k views

Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible. Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...
29
votes
3answers
2k 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$, ...
21
votes
1answer
1k 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 ...
18
votes
4answers
2k 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 ...
10
votes
3answers
2k views

Complexity of computing matrix rank over integers

Does computing the rank of an integer matrix have complexity polynomial in the size of the input? The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and ...
31
votes
1answer
1k views

Is this conjecture strictly weaker than P=NP?

My three computability questions are related to the following group theory question (first asked by Bridson in 1996): For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
18
votes
4answers
770 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 ...
11
votes
0answers
1k views

The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input. Are ...
7
votes
2answers
5k 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: ...
6
votes
2answers
2k views

Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
24
votes
4answers
6k views

How do we know that P != LINSPACE without knowing if one is a subset of the other?

I've seen that P != LINSPACE (by which I mean SPACE(n)), but that we don't know if one is a subset of the other. I assume that means that the proof must not involve showing a problem that's in one ...
19
votes
3answers
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 sub-...
17
votes
1answer
909 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 ...
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 ...
11
votes
2answers
1k 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 ...
7
votes
3answers
2k 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
397 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 (NP-...