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.
1,300
questions
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
- 2,683
13
votes
1
answer
468
views
Real numbers with given complexity
This may be an easy question or it may be related to a well known open problem in Computer Science.
Let $\alpha>0$. We say that $\alpha$ is computed in time $T(n)$ if there is a Turing machine ...
user6976
13
votes
1
answer
644
views
Would efficient factoring have any *other* useful applications?
This question is certainly somewhat opinion-based, but hopefully not hopelessly so.
The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) ...
- 1,243
13
votes
1
answer
1k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
user56218
13
votes
1
answer
591
views
Space Bounded Communication Complexity of Identity
$\bf Definition.$ We define the space bounded communication in the following way. A and B are
supernatural beings capable of computing anything but
they only have a limited amount of memory and that ...
- 18.4k
13
votes
1
answer
680
views
Most computationally efficient Littlewood-Richardson rule
There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the ...
- 1,899
13
votes
1
answer
939
views
Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?
It is well known that every partial order on a set can be extended
to a linear order on that set. That is, for every partial order
$\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such
that ...
- 225k
13
votes
1
answer
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 ...
user10891
13
votes
1
answer
375
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
- 5,380
13
votes
0
answers
214
views
Primitive recursive and feasible presentations for nonstandard models of arithmetic
Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \...
- 17.1k
13
votes
0
answers
703
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
- 3,887
13
votes
0
answers
2k
views
How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?
EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
Here are Vinay Deolalikar's paper, and Richard Lipton's first post ...
- 5,362
12
votes
2
answers
449
views
Testing whether two elements of $\text{SL}(2, \mathbb{F}_{2^n})$ generate the entire group
Given two elements $A,B \in \text{SL}(2, \mathbb{F}_{2^n})$, is there a (computationally inexpensive) test one could perform to check whether together they generate the entire group?
- 223
12
votes
2
answers
3k
views
Is the solution bounded Diophantine problem NP-complete?
Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given ...
- 2,721
12
votes
2
answers
4k
views
How to compute all irreducible representations of a finite group ? (how GAP is doing this?)
Let us "take" a finite group G. Here "take" I mean any type of group-theoretic description you prefer: e.g. as an explicit subset of GL (or other group) or Cayley table, whatever.
Question: How ...
12
votes
2
answers
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 ...
12
votes
2
answers
9k
views
NP not equal to SPACE(n)
Exercise 3.2 of Computational Complexity, a Modern Approach states:
Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.]
I don't know how to solve this problem.
It's in ...
- 643
12
votes
2
answers
3k
views
Can the Legendre symbol be calculated in polynomial time?
Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
- 7,573
12
votes
2
answers
3k
views
What impact would P!=NP have on the characterization of BQP?
Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
- 267
12
votes
4
answers
3k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 3,887
12
votes
1
answer
657
views
Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$
Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free.
In them he ...
- 123
12
votes
2
answers
961
views
Drawing 3-configurations of points and lines with straight lines
It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane....
- 784
12
votes
2
answers
286
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 ...
- 333
12
votes
2
answers
587
views
Faster multiplication with a restricted set of multiplicands?
Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...
- 3,809
12
votes
2
answers
420
views
Techniques for proving relaxed one-wayness of functions
Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...
- 2,951
12
votes
1
answer
539
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 ...
- 2,254
12
votes
1
answer
564
views
Are there very strongly pseudorandom permutations?
A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a ...
- 28.7k
12
votes
1
answer
2k
views
Computing exponential sums rapidly?
I am looking at sums of the form
$\sum_{N\le n \leq N+M} e(P(n))$
where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large).
The question is - when can one ...
- 19.3k
12
votes
0
answers
432
views
Geometric complexity theory for finite fields
Geometric complexity theory (GCT) is an approach via algebraic geometry and representation theory towards the P vs. NP problems and related problems Ketan D. Mulmuley.
More precisely, the idea is to ...
- 2,683
12
votes
0
answers
888
views
Primes and Parity
This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in $...
- 24.2k
11
votes
5
answers
4k
views
Characterize P^NP (a.k.a. Delta_2^p)
What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$.
Obviously $\text{...
- 203
11
votes
4
answers
3k
views
Computational complexity of finding the smallest number with n factors
Given $n \in \mathbb{N}$, suppose we seek the smallest number $f(n)$ with
at least $n$ distinct factors,
excluding $1$ and $n$.
For example, for $n=6$, $f(6)=24$,
because $24$ has the $6$ distinct ...
- 149k
11
votes
2
answers
2k
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 ...
- 2,362
11
votes
5
answers
2k
views
Zero knowledge proof of equality
Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
- 2,937
11
votes
1
answer
670
views
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...
- 12.6k
11
votes
1
answer
884
views
Computational complexity of computing simplicial homology
Is there any literature regarding the fastest known algorithm to compute the homology groups of a simplicial complex (on n vertices)? What about computing the fundamental group? The context is to tell ...
- 123
11
votes
2
answers
2k
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 ...
- 841
11
votes
1
answer
853
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
- 1,088
11
votes
3
answers
482
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 ...
- 24.2k
11
votes
2
answers
649
views
What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?
Disjoint sets $A$ and $B$ are computably inseparable, if there
is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The
existence of c.e. computably inseparable ...
- 225k
11
votes
1
answer
2k
views
Does EXP $\in$ P/poly imply NP=RP?
I guess the answer is that this unknown.
Maybe this implies some "lowness" result on NP relative to BPP?
11
votes
3
answers
4k
views
Is this a well known NP-complete problem?
I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.
Given a directed ...
- 111
11
votes
1
answer
651
views
Descriptive complexity theoretic-characterizations of P and NP
Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material.
The major successes of Descriptive Complexity include Fagin's ...
- 1,909
11
votes
2
answers
2k
views
How hard is it to solve SAT if the promise is that it has an odd number of solutions?
SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...
- 18.4k
11
votes
1
answer
351
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 16.3k
11
votes
3
answers
2k
views
Do you know a faster algorithm to color planar graphs?
while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.
The program can be ...
- 351
11
votes
1
answer
420
views
Comparing two numbers given their factorization
I'm not an expert, but given the integer factorization of two numbers $a,b$:
$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$
What is the time and space compexity of ...
- 1,602
11
votes
2
answers
1k
views
An algorithm to find non-trivial linear dependencies
This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To ...
- 56.2k
11
votes
1
answer
416
views
The complexity of the leading fractional bit of a power of a rational number
On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...
- 4,626
11
votes
1
answer
399
views
Traveling Salesman Problem on finite group
Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying:
$f(x) = 0 \iff x = e$ is the identity;
$\forall x \in H$, we have $f(x) = f(x^{-1})$...
- 12.2k