Questions tagged [natural-proofs]
The natural-proofs tag has no usage guidance.
14
questions
2
votes
0
answers
95
views
Natural proofs and size of propositional formulas
Given a formula $\phi$ of propositional logic, we define its size $|\phi|$ as the number of proposition symbols that $\phi$ contains (counted with multiplicity). For example, $|(p \land p)| = 2$.
Let $...
- 938
0
votes
0
answers
107
views
Does Descriptive Complexity techniques have the naturalisation barrier?
I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise?
By naturalise I'm talking about the Idea of Natural ...
- 21
0
votes
1
answer
107
views
Validity of a modal argument about "vagueness"
(2nd version to make explicit my implicit assumptions about A, B and C, and the definitions of the non-logical constants "⊂" and "≡".)
Intuitively, the following modal argument ...
- 117
6
votes
0
answers
183
views
Converse to natural proofs theorem?
Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'.
Is it easy to see the converse 'if there is no $2^{n^\...
- 12.8k
4
votes
0
answers
97
views
Sampling Functions Efficiently vs Pseudorandom Generators
Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
- 1,062
15
votes
0
answers
511
views
Williams' Method, Natural Proofs and Constructivity
I have some questions on the previous question which is written bellow.
Natural Proof and Constructivity : The topic of the previous question
Recently, Ryan Williams proved that Constructivity in ...
- 171
11
votes
0
answers
538
views
Has there been any result which does not have any Natural Proofs?
Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994).
Has there ...
- 11k
14
votes
0
answers
305
views
Pseudorandom functions in ACC^0?
In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
- 1,344
29
votes
1
answer
1k
views
Toy examples for barriers to $P \ne NP$
Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?
- 2,208
18
votes
2
answers
3k
views
Hierarchy theorem for circuit size
I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.
Is it an interesting approach to class separation?
The motivation for the question is that we ...
- 445
0
votes
1
answer
211
views
quasiP-Natural Property again SIZE($n^e$) for fixed e.
The Natural Proof theorem says :
If for a fixed $c>1$ $G_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against ...
- 445
6
votes
0
answers
172
views
Distributions over circuits and N-to-N vs N-to-1 circuits
This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
- 969
15
votes
1
answer
897
views
Random monotone function
In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...
- 21.5k
15
votes
2
answers
1k
views
Barriers and Monotone Circuit Complexity
Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit ...
- 10.6k