All Questions
1,808 questions
3
votes
1
answer
457
views
How do you handle numerical issues when converting optimization problems to decision problems?
The trick of converting an optimization problem to a decision problem is well-known - you add a real number input to the decision problem for thresholding.
For example, this is taken from Wikipedia ...
- 31
1
vote
0
answers
259
views
Self-improvement property of optimazation problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,993
33
votes
19
answers
6k
views
What is the easiest randomized algorithm to motivate to the layperson?
When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but ...
- 1,088
9
votes
0
answers
2k
views
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, ...
- 24.8k
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
8
votes
3
answers
947
views
Boolean Cube of Primes
For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...
- 273
6
votes
2
answers
2k
views
An Alternative to the Cook-Levin Theorem
In general to prove that a given problem is NP-complete we show that a known NP-complete problem is reducible to it. This process is possible since Cook and Levin used the logical structure of NP to ...
- 115
27
votes
3
answers
2k
views
Why do statistical randomness tests seem so ad hoc?
Wikipedia describes Kendall and Smith's 1938 statistical randomness tests like this:
The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, ...
- 595
2
votes
0
answers
281
views
Recovering a piecewise affine function
Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:
Computing $f(x_1,x_2)$.
Computing a subgradient to $f$ at $(x_1,x_2)$
Computing all ...
- 567
6
votes
2
answers
691
views
Can knowing ahead the length of 3-SAT instance really help?
If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso:
Give me first $n$ the length of your 3-SAT formula, then give me some time on my own ,...
- 1,306
1
vote
3
answers
268
views
Where does the game-theoretic characterization of PH come from?
I have read in a few places that $\mathbf{PH}$ can be interpreted in terms of the complexity of determining the winner in two-player games. I would like to know a) the original reference for this ...
- 15.4k
4
votes
1
answer
248
views
Constructing hard inputs for the complement of bounded halting
If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
\text{coBHP}=\{\...
20
votes
4
answers
870
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 ...
- 85.6k
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,791
9
votes
7
answers
690
views
nonasymptotic complexity results
I recall hearing about a result, or maybe a cluster of results, in some area of complexity theory, probably algebraic, to the effect that there are known, specific, short formulas whose minimal ...
- 1,387
3
votes
0
answers
538
views
Does $EXP\neq ZPP$ implies sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof:
if $EXP\...
12
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,392
22
votes
5
answers
5k
views
Why relativization can't solve NP !=P?
If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...
- 581
18
votes
2
answers
3k
views
Is #k-XORSAT #P-complete?
k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable. Here $\oplus$ denotes the binary XOR operation, $I$ is some index set, ...
- 2,350
16
votes
4
answers
3k
views
Zero-knowledge proof of positivity
If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...
1
vote
3
answers
2k
views
A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm
Let $L$ be a language in $NP$. Then are there any results on whether there exists a polynomial-time algorithm (polynomial in the length of the description of $L$) to decide whether $L \in P$? Are ...
- 601
8
votes
1
answer
653
views
Interesting complexity classes $PR \subsetneq c \subsetneq R$
I'm working on a proof-checker that can verify termination proofs. The fundamental method it provides for constructing such proofs is to translate the program into primitive recursion. Basically, I ...
- 223
14
votes
7
answers
3k
views
Most 'obvious' open problems in complexity theory
What open problems in computational complexity theory have the most 'obvious' answers, regardless of whether that answer is true or false? The problems I'm talking about certainly have more 'obvious' ...
8
votes
1
answer
873
views
P/poly algorithm for polynomial identity testing
By the Schwartz–Zippel lemma, "Is this arithmetic formula identically zero?" is in coRP $\subseteq$ BPP $\subset$ P/poly, with the second inclusion by Adleman's theorem. By basically following the ...
user5810
2
votes
1
answer
1k
views
Does P≠NP over ℝ imply P≠NP ?
Does P≠NP over ℝ imply P≠NP ?
where ℝ is for Real number algorithms as described by Smale with a suitable formulation of P≠NP over ℝ.
Complexity Theory and Numerical Analysis, Steve Smale, 2000
...
- 89
2
votes
2
answers
640
views
Sorting a binary matrix diagonal in polynomial time while preserving rows
Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...
- 121
28
votes
2
answers
2k
views
Is there a syntactic characterization for BPP, BQP, or QMA?
Background
The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The ...
- 5,502
4
votes
1
answer
264
views
Use of randomness in constant parallel time
Let AC0 be the set of decision problems solvable by a logspace-uniform family of constant-depth, polynomial-width boolean circuits with unbounded fanin. Let BPAC0 be the modification of AC0 allowing ...
user5810
2
votes
0
answers
2k
views
Quantum computation implications of (P vs NP) [duplicate]
Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?
Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that P!=...
- 267
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
3
votes
1
answer
1k
views
P not eq. NP news?: [closed]
"Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt). Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving ...
- 10.8k
3
votes
2
answers
2k
views
Practical use of probability amplification for randomized algorithms
Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial ...
- 273
0
votes
1
answer
1k
views
For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?
Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
- 135
11
votes
1
answer
661
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 ...
- 2,009
6
votes
1
answer
384
views
Collapsing of exptime and alternation bounded turing machine
Hello
Let C be a set of function (let say time-computable increasing function to avoid pathological cases).
Let's call $\rm{ATIME}(C,j)$ the class of langages decided by a Turing Machine begining in ...
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?
2
votes
0
answers
637
views
What effect would a proof of P≠NP have on the field of complexity theory?
This question is motivated by Scott Aaronson's comment about his bet: "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it."
http://...
- 89
5
votes
2
answers
2k
views
Horn clauses and satisfiability
It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation.
But suppose we relax the condition for horn clauses from at most one un-negated ...
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,502
9
votes
3
answers
2k
views
When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$? [closed]
From time to time, people announce papers claiming to have settled long open problems like $P$ vs. $NP$. There have been many attempts, reading them is time-consuming, and finding bugs in their ...
13
votes
2
answers
4k
views
A language complete for NP intersection co-NP
Hi,
Is there any language $L$ know to be complete for $NP \cap co-NP$, i.e. any language $L^{\prime} \in NP\cap co-NP$ reduces in polynomial-time to $L$ and it is known that $L\in NP\cap co-NP$?
...
- 601
14
votes
2
answers
750
views
Correct to characterise NP set as P-time image of P set?
[I'm not familiar with the terminology, so when I write P (resp. NP) set, I mean a subset of the integers whose membership function is a decision problem in P (resp. NP).]
Is it correct to say that a ...
- 2,885
7
votes
3
answers
2k
views
Decidable but nonrecursive sets
Until recently, I believed that recursive=decidable,
subscribing to this Wikipedia quote:
"In computability theory, a set is decidable, computable, or recursive if there
is an algorithm that ...
- 151k
16
votes
5
answers
4k
views
What are the most important results (and papers) in complexity theory that every one should know?
A few years ago Lance Fortnow listed his favorite theorems in complexity theory:
(1965-1974)
(1975-1984)
(1985-1994)
(1995-2004)
But he restricted himself (check the third one) and his last post is ...
9
votes
3
answers
3k
views
Complete problems for randomized complexity classes
It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized ...
- 273
1
vote
0
answers
576
views
Minimizing quadratic form over permutations
Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:
$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,
where $S_n$ ...
- 1,839
6
votes
4
answers
2k
views
Examples of Super-polynomial time algorithmic/induction proofs?
In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:
-The proof moves through stages
-An invariant is shown to hold by induction from previous stages
-...
- 1,088
0
votes
1
answer
1k
views
Existence of a pseudo-polynomial time algorithm for a counting problem.
Let T={1,...,n} be a set of tasks. Each task i has associated a non negative processing time p_i and a deadline d_i. A feasible schedule of the tasks consists of a permutation of n elements pi, such ...
- 27
16
votes
3
answers
2k
views
Are there any known quantum algorithms that clearly fall outside a few narrow classes?
I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...
- 15.4k
6
votes
3
answers
475
views
Complexity of high-order differentiation
Let $g(x) = \exp(f(x))$. Assuming numerical (or symbolic) values of $f(x), f'(x), f''(x), \ldots, f^{(n)}(x)$ are known, is there a way to compute $g'(x), g''(x), \ldots g^{(n)}(x)$ (or even the ...
- 2,235