<p>In <a href="http://blog.computationalcomplexity.org/2006/10/focs-funding-music-and-talks.html" rel="nofollow noreferrer">here</a> it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. </p>

<ol>
<li><p>What is the rationale (at least then) behind his $NC^2=P^{\#P}$ program (Valiant is a reputed researcher) which most researchers believe is false?</p></li>
<li><p>Is his program for proving $NC^2=P^{\#P}$ taken seriously and if so what is the status of his program?</p></li>
<li><p>Is this talk available any where?</p></li>
</ol>

<p>I am aware of holographic alorithms. But typically  an inventor invents something because he believes in some vision and not the other way.</p>

CC BY-SA 3.0
2017-07-12T23:05:29.437Z
I know precisely nothing about this, but it's quite easy to see that this refers to the talk Valiant gave for his FOCS 2006 paper https://doi.org/10.1109/FOCS.2006.7
Sasho Nikolov
CC BY-SA 3.0
2017-07-17T18:29:47.587Z
"But typically an inventor invents something because he believes in some vision and not the other way." I'm not so sure about that; cf. Dyson's "[Birds and Frogs](http://www.ams.org/notices/200902/rtx090200212p.pdf)". Also, if I understand the history correctly, Valiant came up with holographic algorithms because he was looking for a subset (possibly all) of quantum algorithms that could be efficiently simulated classically. And then they led to these very surprising results.
Joshua Grochow
CC BY-SA 3.0
2017-07-17T19:05:12.470Z
@JoshuaGrochow 'subset (possibly all) of quantum algorithms ' so he was looking for something big (possibly at least $BQP=RP$).
Turbo
<cc.complexity-theory><reference-request><complexity-classes><big-picture><polynomial-hierarchy>
On status of Valiant's $NC^2=P^{\#P}$ provability program?
Turbo
# On status of Valiant's $NC^2=P^{\#P}$ provability program?

(Asked by: username_0 on 2017-07-12)

In [here](http://blog.computationalcomplexity.org/2006/10/focs-funding-music-and-talks.html) it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back.

1. What is the rationale (at least then) behind his $NC^2=P^{\#P}$ program (Valiant is a reputed researcher) which most researchers believe is false?
2. Is his program for proving $NC^2=P^{\#P}$ taken seriously and if so what is the status of his program?
3. Is this talk available any where?

I am aware of holographic alorithms. But typically an inventor invents something because he believes in some vision and not the other way.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, big-picture, polynomial-hierarchy

> **Comments:**
> **username_1**: I know precisely nothing about this, but it's quite easy to see that this refers to the talk Valiant gave for his FOCS 2006 paper https://doi.org/10.1109/FOCS.2006.7  
> **username_2**: "But typically an inventor invents something because he believes in some vision and not the other way." I'm not so sure about that; cf. Dyson's "[Birds and Frogs](http://www.ams.org/notices/200902/rtx090200212p.pdf)". Also, if I understand the history correctly, Valiant came up with holographic algorithms because he was looking for a subset (possibly all) of quantum algorithms that could be efficiently simulated classically. And then they led to these very surprising results.  
> **username_0**: @JoshuaGrochow 'subset (possibly all) of quantum algorithms ' so he was looking for something big (possibly at least $BQP=RP$).  

---

## 0 answers

