Questions tagged [average-case-complexity]
The average-case-complexity tag has no usage guidance.
21
questions with no upvoted or accepted answers
15
votes
0
answers
460
views
What is the evidence for average case separation between EXP and NEXP?
There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
- 2,181
9
votes
0
answers
515
views
Assigning probability to membership in an NP-complete language
Motivation
Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense.
...
- 2,181
9
votes
0
answers
267
views
Are there sampNP-intermediate problems?
I approximately copied the brief "introduction" to average-case complexity theory of NP from my previous question. However, this question is completely different, so please read on
It is conjectured ...
- 2,181
9
votes
0
answers
394
views
Hard-on-Average, Quasi-Polynomial-Time Problems
In a paper by Raphael Pass, he writes (page 162):
... most natural problems that we believe are hard on average for polynomial
time are also believed hard for quasi-polynomial time.
In another post ...
- 16.6k
8
votes
0
answers
637
views
A generalisation of one-wayness
$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
- 119
7
votes
0
answers
229
views
Relationships between Descriptive Complexity and Average Case Complexity
Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
- 1,261
7
votes
0
answers
137
views
Can relativization technique be applied to natural NP-complete languages?
Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
user17918
6
votes
0
answers
293
views
Quantum computer versus Random 3-SAT?
It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
- 862
5
votes
0
answers
175
views
Hard instances in Impagliazzo's Heuristica
In Impagliazzo's imaginary world Heuristica, P ≠ NP but all NP problems are easy on average for any samplable probability distribution.
In Impagliazzo's paper, he implies that if you do manage to ...
- 7,590
5
votes
0
answers
111
views
Optimal polynomial time algorithm to determine if a random graph is $k$-colorable
Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
- 451
5
votes
0
answers
89
views
Computational depth and p-time hard instances
After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
5
votes
0
answers
243
views
Non-uniform average-case complexity of NP
It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
- 2,181
4
votes
0
answers
198
views
Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?
at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim.
In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-...
- 41
3
votes
0
answers
106
views
Worst to average case reductions for quantum complexity classes
I am studying worst to average case reductions for different complexity classes.
Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
- 193
3
votes
0
answers
223
views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
- 2,110
3
votes
0
answers
95
views
Closest Vector Problem with sparse basis and target vector
The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
- 2,055
2
votes
0
answers
41
views
definition of P-samplable distribution that allows non-binary fractions
Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
2
votes
0
answers
237
views
Height of randomly built binary search tree by insert and delete?
In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
1
vote
0
answers
167
views
Average case hardness of #SAT
Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.
We know that in the worst case, it is #P-complete, but what can we say about an average ...
- 11
1
vote
0
answers
181
views
On planar $4$ regular graphs
It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored.
Is an exact algorithm possible that under uniform distribution is in average polynomial time?
- 13.2k
1
vote
0
answers
70
views
Average case or beyond worse case analysis for non-convex optimization procedures?
I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature.
It is known that global optimization of non-convex functions is NP-...
- 161