Hacker News new | past | comments | ask | show | jobs | submit login

For most of this problems that they mention you need AGI, we do not know how to attack this problem also.

Solving any coding challenge is NP-hard problem. You need to understand not only what you need to do but also how language in which you need to do it works. For example in game of Go you have huge amount of possible states but you have only couple of moves to transition to this states. In programming language every line of code has large space of states and it grows exponentially with every new line of code. Sure you can brute force "hello world" program but good luck with writing 1000 lines of code that work together to solve complex problem. Pattern matching will not help you, training based on github will not help you.

Hi, I'm a researcher in program synthesis.

I think you meant to say "NP-hard" . And indeed, there are many program synthesis problems which are NP-hard, 2EXP-complete, or undecidable. But there are also many program synthesis algorithms which are polynomial time. If you use Windows, there might even be one running on your computer.

We've been studying this problem for close to 50 years. I think you see the basic problems, but we know a lot about what to do about them.

> If you use Windows, there might even be one running on your computer.

Which algorithm / program is this?

Maybe OP means Excel's FlashFill[1]? It's a feature that figures out string manipulations based on a handful of examples, and it pretty much went directly from MSR research on program synthesis into Excel 2013.

[1]: http://research.microsoft.com/en-us/um/people/sumitg/flashfi...

FlashFill, a feature in Microsoft Excel.

Indeed, NP-hard (edited it now). Can you expand on "we know a lot about what to do about them" ? Thanks.

So first, NP-hard isn't much of a barrier. We often like to call it "NP-easy." Or, going a step further:

"PSPACE-complete is great news. It's the new poly-time." -- Moshe Vardi

SAT solvers are very fast. It's worst-case exponential, sure, but it's hard to find that worst-case. I just heard at lunch yesterday that MaxSAT is now also easily handling problems with millions of variables. I think I'd be scared if I found out what the record was for normal SAT.

So, how do you actually do synthesis? I could talk for quite a while about it.....but here's a pretty good intro-article: https://homes.cs.washington.edu/~bornholt/post/synthesis-for...

It's worst-case exponential, sure, but it's hard to find that worst-case.

It's not that hard. Just generate a boolean circuit for the multiplication of 2 64 bit prime numbers and convert the circuit to a 3-SAT formula. I doubt any current SAT solver can solve that problem. If you could do it for 1024 bit primes a lot of cryptography would be toast.

EDIT: To be a bit more clear I mean that the circuit takes two n-bit numbers, multiplies them then compares the result to some known product of 2 primes. So by solving this circuit you factor the known integer.

EDIT2: Doesn't solving MaxSAT exactly imply that you can also solve SAT ? If there's a SAT solver that can handle million variable instances "easily" that's something I'd be really interested in hearing more about.

The satisfiability problem doesn't require that you provide the solution, only that you determine whether or not a solution exists. So you'd end up with a primality check, which is known to be in P:


It's not a primality test. A primality test determines whether or not a single given integer is prime.

The circuit I described checks that the product of two arbitrary input integers is a specific known integer.

By solving the decision problem for each bit independently you can determine all bits of the 2 input integers and hence factor the known target.

Neat. I wasn't aware of the trick of peeling off a bit at a time.

Relatedly, even though Boolean Satisfiability [1] is NP-complete, there are SAT solvers that can solve huge practical instances fast enough to be useful.

1: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

Solving any coding challenge is NP-hard problem.

To prove that statement you'd have to carefully define your terms.

If "Develop a polynomial time algorithm to determine whether any given 3SAT problem is satisfiable" is a valid coding challenge then the statement is obviously true.

On the other hand I doubt that solving the types of coding challenges that actually appear in competitions can be proven to be NP-hard because that would prove that humans are much better at solving NP-hard problems than any currently known algorithm. I don't think there is any such proof (though there may be some weak evidence for the proposition).

It'd be useful-enough to have an AI that could be given problem descriptions of the first kind (problem-statements that describe problems which may or may not require original research to solve), and then manage to figure out whether they reduce to gluing a set of "known" solutions together (and then, perhaps, generate such solutions), or whether they require original scientific/mathematical research (at which point it could just shrug its digital shoulders, like most humans do at that point.)

And by "known", I don't mean "in the AI's knowledge-base"; the AI would properly at least be able to hunt down textbooks and journal papers, read them, and learn problem-solving approaches from them. In other words, the AI would at least be as able to "do science" in the way that a grad student is expected to "do science."

I think any algorithm that could do that would count as an artificial general intelligence (AGI) and I think the current consensus is that we currently have no idea how to create one.

What relation an AGI has to NP hardness is unclear. I think that if P=NP in the sense that a practical algorithm exists for solving large (ie. 10^9 variables) NP complete problems then AGI (even super-AGI) would probably follow. However I don't necessarily think that's a necessary condition for AGI to exist.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact