4 ms·

We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization. It's kind of trivial to say it's in NP because we can verify in

We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization. It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!! I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)

SJC_Hacker 3y ago
I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel. So maybe it should really be P and NDP.
- keepamovin 3y ago
  That's a good explanation. I didn't know that.
- eru 3y ago
  > or alternatively, a function executing on all inputs in parallel. I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses). But as long as your parallel executions don't interact at all, the definitions are identical, I think.
eru 3y ago
> We don't know that factorization is NP-complete. Yes? No one ever said it was. None of the common cryptographic problems are expected to be NP-complete, even if they aren't in P. That's because they are known to be in both NP and in co-NP, and it's expected that NP != co-NP. > I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". In what sense is that a 'better' definition than the standard definition? It sounds like what you are talking about is NP\P (where \ is set subtraction, ie 'NP minus P').
- keepamovin 3y ago
  I think some people have asked whether it was. I'm not saying you did, just thought it was interesting! Haha :) I don't even know what co-NP is. Could you explain? I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Yeah, I guess what you're saying about NP\P is right in that it's a restatement of the definition of what I said, haha! I'm not an expert this is just what I think :)
  - eru 3y ago
    > I don't even know what co-NP is. Could you explain? See https://en.wikipedia.org/wiki/Co-NP https://en.wikipedia.org/wiki/Co-NP That article even mentions integer factorisation. > I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Well, that's a non-standard definition for NP, and you would have a hard time talking to anyone. And at the moment we have no clue whether your 'NP' has any problems in it at at all, or whether it's an empty set. In that sense, it's a very impractical definition. Btw, there's some nice alternative but equivalent definitions for traditional NP. The classic definition is basically, NP are those problem that you can check in polynomial time if someone gives you a hint (ie they give you the answer and whatever else you need, but you need to verify, you can't trust the hint.) A nice alternative definition says that with access to randomness, that hint needs to be at most O(log n) long, and you also only need to even look at 3 randomly chosen bits of that short hint, and you are still guaranteed to suss out any fake answer with at least 66% probability. See https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/PCP_theorem
    - keepamovin 3y ago
      Thanks for the alt NP definition. I'd be fine to talk to people we just have to clarify the definitions first. Haha! :) I think mine's good but I get if you differ, no worries. It's actually a very fascinating definition and question: Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions? I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively?? For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea. That is, co-NP is the set of decision problems where there exists a polynomial {\displaystyle p(n)} and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by {\displaystyle p(n)}, the Turing machine M accepts the pair (x, c).

SJC_Hacker 3y ago

I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel. So maybe it should really be P and NDP.

keepamovin 3y ago
That's a good explanation. I didn't know that.
eru 3y ago
> or alternatively, a function executing on all inputs in parallel. I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses). But as long as your parallel executions don't interact at all, the definitions are identical, I think.

eru 3y ago

> We don't know that factorization is NP-complete. Yes? No one ever said it was. None of the common cryptographic problems are expected to be NP-complete, even if they aren't in P. That's because they are known to be in both NP and in co-NP, and it's expected that NP != co-NP. > I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". In what sense is that a 'better' definition than the standard definition? It sounds like what you are talking about is NP\P (where \ is set subtraction, ie 'NP minus P').

keepamovin 3y ago
I think some people have asked whether it was. I'm not saying you did, just thought it was interesting! Haha :) I don't even know what co-NP is. Could you explain? I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Yeah, I guess what you're saying about NP\P is right in that it's a restatement of the definition of what I said, haha! I'm not an expert this is just what I think :)
- eru 3y ago
  > I don't even know what co-NP is. Could you explain? See https://en.wikipedia.org/wiki/Co-NP https://en.wikipedia.org/wiki/Co-NP That article even mentions integer factorisation. > I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Well, that's a non-standard definition for NP, and you would have a hard time talking to anyone. And at the moment we have no clue whether your 'NP' has any problems in it at at all, or whether it's an empty set. In that sense, it's a very impractical definition. Btw, there's some nice alternative but equivalent definitions for traditional NP. The classic definition is basically, NP are those problem that you can check in polynomial time if someone gives you a hint (ie they give you the answer and whatever else you need, but you need to verify, you can't trust the hint.) A nice alternative definition says that with access to randomness, that hint needs to be at most O(log n) long, and you also only need to even look at 3 randomly chosen bits of that short hint, and you are still guaranteed to suss out any fake answer with at least 66% probability. See https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/PCP_theorem
  - keepamovin 3y ago
    Thanks for the alt NP definition. I'd be fine to talk to people we just have to clarify the definitions first. Haha! :) I think mine's good but I get if you differ, no worries. It's actually a very fascinating definition and question: Are there problems for which we can prove they are in NP but also prove they cannot have polynomial time (P time) solutions? I did check out that wiki page first, but found it super difficult to parse. Do you have some insight that could help me understand more simply/intuitively?? For instance, I found the definition of NP as P if you have an NFA, to be super easy to understand. But when that wiki starts talking about "certificates" I just have no idea. That is, co-NP is the set of decision problems where there exists a polynomial {\displaystyle p(n)} and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by {\displaystyle p(n)}, the Turing machine M accepts the pair (x, c).