All Questions
1,809 questions
1
vote
2
answers
545
views
Complexity of Max Bisection on cubic planar graphs?
Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximized. Max Bisection is $NP$-complete on cubic graphs and also on planar ...
- 2,993
7
votes
4
answers
884
views
Is the classification of finite p-groups a smooth problem?
Fix a prime $p$. Then the question is about the difficulty of classifying finite $p$-groups. Originally I was going to ask if this was a "wild" problem but thanks to Joel David Hamkins' answer to ...
- 9,132
2
votes
1
answer
201
views
Are the following to problems in RL complexity class? Proof outline?
L={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v}
R={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v, and at ...
- 29
0
votes
2
answers
1k
views
Degenerate case of linear programming duality?
Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{...
- 2,019
5
votes
8
answers
6k
views
Independence of P = NP?
Let's suppose P = NP is independent (of ZFC). Then there is a model of ZFC in which there is a polynomial time algorithm for SAT. But suppose this algorithm is correct, wouldn't this algorithm exist ...
- 551
2
votes
1
answer
403
views
Finding a 5-cycle in a sparse graph efficiently.
Hi,
I was reading this thread: Finding a cycle of fixed length
I want to find a 5-cycle in a graph. Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a ...
- 1,834
7
votes
1
answer
2k
views
Is pattern recognition NP-complete?
Hello,
is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) ...
- 233
0
votes
1
answer
229
views
weaker oracle machine ?
My question is the following:
Can a (probabilistic, deterministic, ndtm) oracle turing machine $A$ calling an oracle residing in a superior (more difficult) complexity class $B$, have less power then ...
- 103
8
votes
4
answers
2k
views
Zero-knowledge proof that 0 = 1
Suppose one day I came up with a proof that 0 = 1 in some formal system such as PA or ZFC that cannot prove its own consistency (unless it is inconsistent). Would it be possible to have a zero-...
46
votes
8
answers
5k
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 ...
- 12.7k
3
votes
0
answers
359
views
Do Isometry Groups Tell Us How Difficult Norms are to Compute?
The question: Consider two norms N1 and N2 on the space of n-by-n complex matrices. N1 and N2 have the same isometry group and computing N1 is NP-HARD. Does it follow that computing N2 is NP-HARD as ...
- 6,351
35
votes
8
answers
4k
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 ...
- 3,267
6
votes
1
answer
516
views
Poincare conjecture and the graph of triangulations
This was an update to this question, but I decided to make it a separate question. The definition of the graph of triangulations can be found in the previous question.
Question. I was told a few ...
user6976
14
votes
2
answers
2k
views
The flip graph of triangulations
A polygon $P_k$ divided by $k-2$ diagonals into triangles is called a polygonal triangulation. These are the vertices of the triangulation graph $\mathcal P_k$. Two vertices are connected by an edge ...
user6976
4
votes
2
answers
425
views
Derandomizing BPP (bounded-error probabilistic polynomial time)
What's the best result about derandomizing BPP which based on some uniform assumptions?
For instance, has someone proved that BPP can be simulated in subexp time if EXP $\not =$ BPP?
- 41
3
votes
0
answers
770
views
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
- 15.4k
1
vote
1
answer
231
views
Hardness of discrete geometric area minimization problem?
This question was originally posted on: cstheory.stackexchange
Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.
...
- 2,993
2
votes
1
answer
857
views
What is the relationship between singular value decomposition and solving linear systems?
It is known that solving systems of linear equations is reducible to SVD in a straightforward way; if you want to solve $\mathbf{Ax}=\mathbf{b}$, then you can perform SVD on $\mathbf{A}$ and minimize $...
- 2,019
2
votes
0
answers
143
views
finding set of tree decompositions to cover all pairs of vertices
I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...
- 2,442
2
votes
0
answers
289
views
Finding globally minimal row subsets of an integer matrix which generate the full row span
Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is ...
- 5,654
13
votes
6
answers
3k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
7
votes
3
answers
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 ...
- 23k
8
votes
0
answers
753
views
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?
I know it is NP-complete for the ...
- 161
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
- 1,164
4
votes
1
answer
190
views
hardness of identifying the number of local maxima for mixture of Gaussians
I once may have heard (but I may misremember or misunderstand), that the problem of deciding how many local maxima a mixture of Gaussians has is NP-hard.
Is this true, or is the hardness of this ...
- 41
2
votes
1
answer
1k
views
Linear Programming Cost Function [closed]
I need to add the following to my LP problem:
If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2.
Example: if 30 workers are hired in ...
3
votes
3
answers
852
views
A conjecture on a Subset Power Sum Problem motivated by Computer Science
Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such ...
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.6k
3
votes
1
answer
277
views
Theorems about the directed bandwidth of a rooted tree?
Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...
- 4,922
18
votes
2
answers
1k
views
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy
to test for membership but a lot more difficult to find members, and for others
the reverse is true. Here is an elementary ...
- 15.3k
1
vote
4
answers
978
views
Maximum average value within a rectangular bounding box
The goal is to expedite detection using the sliding window approach. In other words, an object classifier is known and I need to find where the possible locations of this object are in an image. This ...
- 111
1
vote
2
answers
1k
views
Inequality-constrained linear-regression, what is the covariance of the estimator?
If you do a linear regression: $||Ax - e ||^2$, where e is iid Gaussian, mean 0 and variance 1, then your answer is $x_{hat} = (A' A)^{-1} (A' * e)$ and the covariance of $x_{hat}$ is $(A' A)^{-1}$
...
10
votes
3
answers
649
views
Efficiently getting bits of N! ?
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
i.e....
- 513
1
vote
2
answers
1k
views
NP-Hard solution question
Hello, i have NP hard problem. Let imagine I have found some polynomial algorithm that find ONLY one of many existing solutions of that problem, but at least one solution (if present in the probem). ...
- 13
3
votes
0
answers
229
views
For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?
Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(...
- 2,442
1
vote
2
answers
3k
views
Analyzing Weighted Set-Cover variant
A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for ...
- 111
0
votes
1
answer
755
views
A few questions about Computational Problems Complexity Classification
(This might look like just a post to you and you might think I shouldn't have submitted it as a question here but in reality it is some questions put together, so I hope you don't close it)
I only ...
- 103
3
votes
2
answers
1k
views
Amplitude amplification as a quantum walk algorithm
This is a followup to an earlier question on a taxonomy for quantum algorithms in which I ultimately concluded in a comment that all known nontrivial quantum algorithm speedups (in Jordan's quantum ...
- 15.4k
5
votes
2
answers
612
views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
4
votes
1
answer
2k
views
How to find which subset of bitfields xor to another bitfield?
I have a somewhat coding-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to ...
- 41
10
votes
0
answers
2k
views
Is Witten's new method of quantization useful for geometric complexity theory?
The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
- 321
15
votes
2
answers
2k
views
What's known about the relationship about EQP and BQP?
EQP is the class of problems solvable deterministically using a quantum computer in polynomial time - that seems to me to be a good analogue to P, whereas BQP is the quantum analogue of BPP.
It ...
- 2,019
27
votes
4
answers
8k
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 ...
- 503
13
votes
0
answers
713
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,897
10
votes
2
answers
3k
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 ...
- 9,114
2
votes
0
answers
313
views
Complexity of a variant of the Mandelbrot set decision problem?
This is a modified version of a question posted on StackExchange TCS.
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define
$M=${$(c,k,r)...
- 2,993
2
votes
4
answers
2k
views
Is there any space(n) complete language?
Does space(n) have a complete language? Actually the following was in a complexity cource final exam :
if A is SPACE(n) hard then A is also PSPACE-hard
(this is supposed to be shown by padding...i ...
- 21
3
votes
1
answer
2k
views
How is #P related to other complexity classes?
The counting class $\text{#P}$ and the related decision class $PP$ both involve counting the number of certificates to $NP$ problems.
Because $\text{#P}$ counts certificates, it seems obvious that $...
- 115
1
vote
1
answer
9k
views
what is the difference between the revised simplex method andthe full tableu?
No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.
- 111