Questions tagged [average-case-complexity]

The tag has no usage guidance.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15 votes
0 answers
458 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 ...
Vanessa's user avatar
  • 2,151
9 votes
0 answers
514 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. ...
Vanessa's user avatar
  • 2,151
9 votes
0 answers
265 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 ...
Vanessa's user avatar
  • 2,151
9 votes
0 answers
392 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 ...
Sadeq Dousti's user avatar
  • 16.5k
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 ...
Pooya Farshim's user avatar
7 votes
0 answers
215 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. ...
user3483902's user avatar
  • 1,261
7 votes
0 answers
135 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 ...
user avatar
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-...
Minkov's user avatar
  • 852
5 votes
0 answers
170 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 ...
Timothy Chow's user avatar
  • 7,550
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 $...
Steve's user avatar
  • 451
5 votes
0 answers
88 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 ...
Ramon Bejar Torres's user avatar
5 votes
0 answers
242 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 ...
Vanessa's user avatar
  • 2,151
4 votes
0 answers
195 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-...
Senf's user avatar
  • 41
3 votes
0 answers
99 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 ...
AngryLion's user avatar
  • 173
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 ...
Matt Groff's user avatar
  • 2,100
3 votes
0 answers
94 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 ...
Ross Snider's user avatar
  • 2,035
2 votes
0 answers
37 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 ...
Shivaram Lingamneni's user avatar
2 votes
0 answers
235 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 ...
Bapi Chatterjee's user avatar
1 vote
0 answers
161 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 ...
arika's user avatar
  • 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?
Turbo's user avatar
  • 12.9k
1 vote
0 answers
69 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-...
Jake Shellman's user avatar