6 ms·

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

by lossolo 10y ago

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.

Darmani 10y ago
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.
- lossolo 10y ago
  Indeed, NP-hard (edited it now). Can you expand on "we know a lot about what to do about them" ? Thanks.
  - Darmani 10y ago
    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-architects.html https://homes.cs.washington.edu/~bornholt/post/synthesis-for...
    - tgflynn 10y ago
      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.
      - mortehu 10y ago
        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: https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
        tgflynn 10y ago
        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.
        mortehu 10y ago
        Neat. I wasn't aware of the trick of peeling off a bit at a time.
  - deleted 10y ago
    [deleted]
  - hcs 10y ago
    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 https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
- nawitus 10y ago
  > If you use Windows, there might even be one running on your computer. Which algorithm / program is this?
  - Darmani 10y ago
    FlashFill, a feature in Microsoft Excel.
  - tikhonj 10y ago
    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/flashfill.html http://research.microsoft.com/en-us/um/people/sumitg/flashfi...
tgflynn 10y ago
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).
- derefr 10y ago
  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."
  - tgflynn 10y ago
    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.
deleted 10y ago
[deleted]

by lossolo 10y ago

Darmani 10y ago

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.

lossolo 10y ago
Indeed, NP-hard (edited it now). Can you expand on "we know a lot about what to do about them" ? Thanks.
- Darmani 10y ago
  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-architects.html https://homes.cs.washington.edu/~bornholt/post/synthesis-for...
  - tgflynn 10y ago
    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.
    - mortehu 10y ago
      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: https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test
      - tgflynn 10y ago
        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.
        mortehu 10y ago
        Neat. I wasn't aware of the trick of peeling off a bit at a time.
- deleted 10y ago
  [deleted]
- hcs 10y ago
  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 https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
nawitus 10y ago
> If you use Windows, there might even be one running on your computer. Which algorithm / program is this?
- Darmani 10y ago
  FlashFill, a feature in Microsoft Excel.
- tikhonj 10y ago
  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/flashfill.html http://research.microsoft.com/en-us/um/people/sumitg/flashfi...

tgflynn 10y ago

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).

derefr 10y ago
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."
- tgflynn 10y ago
  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.

deleted 10y ago

[deleted]