All Questions
1,808 questions
11
votes
1
answer
552
views
complexity of counting homomorphisms
This is a question I have thought about and asked a number of people, but have never got an answer beyond "It should be true that..."
Given a finitely generated group $G$ (eg. a link group $G_L:=\...
- 1,639
0
votes
1
answer
145
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?
- 57
2
votes
2
answers
436
views
NP Complete for range sum constraints?
Is the following problem NP Complete?
We have $n$ variables $x_1$,$x_2$,....,$x_n$ and a set of constraints:
$\sum_{i=a_1}^{b_1}x_i = h_1$
$\sum_{i=a_2}^{b_2}x_i = h_2$
$\sum_{i=a_3}^{b_3}x_i = ...
- 21
10
votes
1
answer
910
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
- 1,288
6
votes
3
answers
2k
views
A simple infinite dimensional optimization problem
I'd be grateful for a reference for the following result, which I believe to be true, and
should be well-known.
Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
- 520
6
votes
2
answers
564
views
Funky congruences
Suppose we have the remainders: {$(a^0_1, a^1_1), \ldots, (a^0_n, a^1_n)$} and the moduli {$c_1, \ldots, c_n$}. We want to know if there exists $b_1, \ldots, b_n \in$ {0,1} and $m \in \mathbb{N}$ such ...
- 265
4
votes
1
answer
274
views
Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?
In complexity theory, when a uniform family of circuits recognises a language is it the case that each of the input gates is on a path to the output gate?
That is, there are no input gates with wires ...
- 339
0
votes
2
answers
2k
views
Time complexity of finding the GCD of a set S as a function of sum(S)
The algorithm to be used is:
Sort the set into ascending order
$x_1 = s_1$
$x_i = gcd(x_{i-1},s_i)$
$GCD = x_n$
What I'm looking for is expected run time as a function of $\sum_{i\in S}i$
As a ...
- 205
5
votes
4
answers
866
views
Reconstructing a fraction from its first digits
It is not difficult to see that any reduced fraction $\frac{p}{q}$
where $0 < p < q $ and both $p$ and $q$ have at most $N$
digits (where $N$ is a fixed integer) can be reconstructed
from its ...
- 3,595
15
votes
3
answers
1k
views
Is this strange problem NP-complete?
The following quadratic expression can be simplified:
(x+1)(x+2) + (x+1)(x-3) + 2x(2x-1) - (3x+1)(x-3) - 2x(x+2).
What is the easiest way of doing the simplification? (It would be good to think ...
- 29k
12
votes
4
answers
4k
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,897
5
votes
1
answer
540
views
Minimal Backtracking Proof Tree
When trying to prove that a particular instance of a problem like graph coloring or SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of ...
- 601
9
votes
4
answers
4k
views
Efficient way of determining isomorphism
Suppose you are given two isomorphic graphs $G$ and $H$. Is there an efficient way of defining an isomorphism $\phi:V(G)
\to V(H)$ if we already know they are isomorphic? Or is it just a guess and ...
- 151
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
68
votes
8
answers
43k
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 ...
- 699
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
0
votes
2
answers
4k
views
Linear programming piecewise linear objective
I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:
max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$
$s.t. $
$|\...
- 3
8
votes
4
answers
999
views
Does IP = PSPACE work over other rings?
Background: It is possible (see e.g., this) to define a Turing machine over an arbitrary ring. It reduces to the classical notion when the ring is $\mathbb{Z}_2$; the key difference is that ...
- 25.6k
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.7k
26
votes
6
answers
9k
views
The problem of finding the first digit in Graham's number
Motivation
In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
- 1,593
4
votes
2
answers
2k
views
Are there any pairing functions computable in constant time (AC⁰)
Are there any known reversible pairing functions $f: \mathbb N \times \mathbb N \to \mathbb N$ that can be computed in constant time (FAC⁰)?
- 339
10
votes
3
answers
1k
views
Is there a formal notion of what we do when we 'Let X be ...'?
This is likely an elementary question to logicians or theoretical computer scientists, but I'm less than adequately informed on either topic and don't know where to find the answer. Please excuse the ...
- 1,376
10
votes
1
answer
2k
views
Sum of difference moduli vs. sum of modulus differences
This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.
Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
- 33.8k
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
46
votes
7
answers
13k
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 ...
- 6,694
3
votes
3
answers
579
views
The limits of parallelism
Is it possible to solve a problem of O(n!) complexity within a reasonable time given unlimited number of processing units and infinite space?
The typical example of O(n!) problem is brute-force ...
- 555
3
votes
0
answers
318
views
Drawing a combinatorial 3-configuration of points and lines with pseudolines
This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us ...
- 784
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
12
votes
2
answers
980
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
8
votes
4
answers
890
views
Does there exist a general theory of "arithmetic complexity"/"arithmetic height"?
This question is hopelessly vague, but here goes:
Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined notion of arithmetic ...
- 5,530
6
votes
1
answer
1k
views
Finding a cycle of fixed length in a bipartite graph
Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...
- 784
11
votes
1
answer
860
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
28
votes
4
answers
5k
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 ...
- 4,994
28
votes
2
answers
3k
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 ...
- 47.3k
13
votes
1
answer
598
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.7k
5
votes
2
answers
457
views
Heaviest Convex Polygon
Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
- 341
29
votes
3
answers
3k
views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
-2
votes
1
answer
519
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 |Q(B)...
24
votes
2
answers
3k
views
Counting subgraphs of bipartite graphs
I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...
- 291
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
6
votes
2
answers
605
views
Complexity class of problems solvable using Q&A site
Motivation
We will be trying to find what is the complexity class of problems solvable by a polynomial time algorithm (poster) that has access to a certain oracle (Q&A site) formalizing certain ...
- 15.1k
6
votes
0
answers
346
views
Enumerating (generalized) de Bruijn tori
Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e.,...
- 15.4k
5
votes
1
answer
2k
views
BPP being equal to #P under Oracle
Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.
In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{...
- 601
29
votes
7
answers
8k
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 ...
- 2,383
7
votes
2
answers
1k
views
How unhelpful is graph minors theorem?
A very interesting Robertson-Seymour (graphs minors) theorem says:
Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$graphs $G$ ...
- 15.1k
22
votes
3
answers
6k
views
Satisfiability of general Boolean formulas with at most two occurrences per variable
(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
- 4,729
18
votes
5
answers
8k
views
What techniques exist to show that a problem is not NP-complete?
The standard way to show that a problem is NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to ...
- 118k
14
votes
2
answers
4k
views
Best-case Running-time to solve an NP-Complete problem
What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
- 597
15
votes
2
answers
3k
views
How to compute the rank of a matrix?
Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.
Here's the actual ...
- 12.6k
24
votes
4
answers
5k
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 ...
- 2,416