Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computational-complexity
Search options answers only
not deleted
user 658
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
vote
Complexity of Max Bisection on cubic planar graphs?
Max-Cut, at least, in cubic graphs is NP-hard even to approximate to some factor .997. This is due to Berman and Karpinski, 1999:
On some tighter inapproximability results. In Proceedings of the 26t …
- 6,694
6
votes
Accepted
Naive question about polynomial time reducibility
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$\text{3SATpad} = \{ \phi \#^{|\phi|^{100}} : \phi \in \text{3SAT}\}$,
where $\#$ is some new symbol. …
- 6,694
4
votes
For interior point methods of linear programming, what is the "L" in the computational compl...
Yes, as you say, both usages occur in the literature, with "total number of bits in the input" being more prevalent in interior point papers. But I guess Vaidya has noticed that one can be more caref …
- 6,694
12
votes
What techniques exist to show that a problem is not NP-complete?
There are several results along these lines known, all of which use one technique: You show that if the problem is NP-complete, then some very strongly believed complexity hypothesis fails. In the fo …
- 6,694
11
votes
Most 'obvious' open problems in complexity theory
The following two statements are really "obviously false", but are still open:
$EXP^{NP} \subseteq$ depth-2-$TC^0$
$EXP^{NP} \subseteq$ depth-2-$AC^0[6]$
Just as a reminder:
$EXP^{NP}$ is expon …
24
votes
Accepted
Characterize P^NP (a.k.a. Delta_2^p)
The standard complete problem for the "function version" of P^NP is to find the lexicographically last satisfying assignment of a given boolean formula. To be more finicky, a complete language for P^ …
- 6,694
171
votes
Accepted
Example of a good Zero Knowledge Proof
The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherw …
- 6,694
4
votes
Degree $d$ function with boolean inputs with small range is a junta?
This is a nice question. I have to think that the answer must appear somewhere, but I'm not sure where.
Here is, I think, a solution for $m = 3$. I guess it could be generalized to any $m$, but po …
- 6,694
25
votes
Equivalent forms of the P vs. NP problem
There is the descriptive complexity formulation:
P = NP is equivalent to the statement that every property expressible by a second order existential statement is also expressible in first order log …
- 6,694
8
votes
What are the strongest arguments for a genuine quantum computing advantage?
As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the Strong Exponential Time Hypothesis (a by-now moderately accepted genera …
- 6,694
3
votes
Accepted
A Boolean function that is not constant on affine subspaces of large enough dimension
Unless I am misreading it, the paper Affine dispersers from subspace polynomials by Ben-Sasson and Kopparty gives an explicit construction which is nonconstant on any affine subspace of dimension less …
- 6,694
5
votes
Accepted
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
To some extent this depends on the model of computation. Some remarks:
The problem must always involve an accuracy parameter $\epsilon$, since in general the answer will not be rational
Even in the …
- 6,694
7
votes
What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at m...
I think it might still be unknown whether the constant can be reduced below $e$. By the Central Limit Theorem, if it can be so reduced, then it can also be reduced below $e$ for functions on Gaussian …
- 6,694
21
votes
Accepted
Satisfiability of general Boolean formulas with at most two occurrences per variable
A theorem in a paper of Peter Heusch, "The Complexity of the Falsifiability Problem for Pure Implicational Formulas" (MFCS'95), seems to suggest the problem is NP-hard. I repeat the first part of its …
- 6,694