### Marco Devillers

Shared publicly -A long nightly read whereas I should have been coding.

I remain undecided.

I disagree with Knuth. I estimate I know where he comes from: Given advances in 3SAT solvers they seem to have broken some magical barrier and P=NP, maybe.

But 3SAT solvers mostly run over translated digital circuits and don't seem to do a lot more than very efficient local reasoning over parts of the graph usually mostly deriving small local facts. That doesn't seem to generalize.

Aaronson's intuition seems to be that (most) algorithms cleanly separate into P or NP and therefore any reduction would have been found by now.

I disagree with that too. What I observe is that people often have some idea about the complexity of an algorithm, say parsing with derivatives - which was believed to be exponential - but then, after analysis, that turns out to be cubic. But never an attempt is made to 'connect' P and NP so I don't believe you can expect a non-trivial reduction between them to pop up. That doesn't seem to make sense either.

I remain thoroughly undecided.

Where I do agree with Aaronson is that I also firmly believe it is time to start brute forcing hints about P?=NP, and especially about digital circuits. It's a cheap approach, it will trivially pay off in publications and new research methods, there are an uncomforting number of unknowns for even the most trivial questions about circuit sizes in various classes, and since everybody is almost completely clueless you can't possibly do worse than anyone else.

Finally, It was pleasing to notice that the latest 'proof' was indeed flawed, as I thought, by trying to generalize a result from randomized SAT instances to structured instances. (My intuition was just based on something you notice if you translate circuits to 3SAT by hand. It's not about clause/variable phase transitions.)

We still don't know doodles. I say brute force it.

I remain undecided.

I disagree with Knuth. I estimate I know where he comes from: Given advances in 3SAT solvers they seem to have broken some magical barrier and P=NP, maybe.

But 3SAT solvers mostly run over translated digital circuits and don't seem to do a lot more than very efficient local reasoning over parts of the graph usually mostly deriving small local facts. That doesn't seem to generalize.

Aaronson's intuition seems to be that (most) algorithms cleanly separate into P or NP and therefore any reduction would have been found by now.

I disagree with that too. What I observe is that people often have some idea about the complexity of an algorithm, say parsing with derivatives - which was believed to be exponential - but then, after analysis, that turns out to be cubic. But never an attempt is made to 'connect' P and NP so I don't believe you can expect a non-trivial reduction between them to pop up. That doesn't seem to make sense either.

I remain thoroughly undecided.

Where I do agree with Aaronson is that I also firmly believe it is time to start brute forcing hints about P?=NP, and especially about digital circuits. It's a cheap approach, it will trivially pay off in publications and new research methods, there are an uncomforting number of unknowns for even the most trivial questions about circuit sizes in various classes, and since everybody is almost completely clueless you can't possibly do worse than anyone else.

Finally, It was pleasing to notice that the latest 'proof' was indeed flawed, as I thought, by trying to generalize a result from randomized SAT instances to structured instances. (My intuition was just based on something you notice if you translate circuits to 3SAT by hand. It's not about clause/variable phase transitions.)

We still don't know doodles. I say brute force it.

More than you ever wanted to know about P=NP.

1

3 comments

Ah. I forgot. The (other) major reason that one proof was flawed is that a phase transition is an experimental result given a specific algorithm, not all possible algorithms. You're using that we need exponential algorithms to solve NP problems

Well, that's what I remember. Long time ago.

*as far as we know*. Circular reasoning.Well, that's what I remember. Long time ago.

Add a comment...