What is the fastest algorithm and its computational complexity to the subset-(bit) AND problem?

[Dubslow]

Originally Posted by a1call

I missed that. I wonder how you could notice.

The poster in question is notorious for it.

[Raman]

Originally Posted by CRGreathouse

That's not believed to hold. This is essentially the statement of Impagliazzo's Heuristica, where we are believed to be in Cryptomania. (See A personal view of average-case complexity.)

Hello, I just quoted a statement from Wikipedia: Common misconceptions about NP-completeness, like
1. For NP-complete problems, most instances can be solved in P.
2. For NP-complete problems, we have algorithms that run in superpolynomial time or subexponential time.
3. NP-complete problems are not the hardest problems, some algorithms need more than (deterministic) exponential running time or are undecidable (the complexity classes PSPACE / EXPTIME / ... exist).
4. Breaking some cryptographic ciphers like AES and DES is in P, but with the large constant in its complexity, running time required to break it will exceed the age of the universe.
5. NP-complete problems can be solved in P under some special cases.

So, you are claiming that Wikipedia is wrong or needs corrections ?!

By the way, I have studied about Impagliazzo's Five Worlds before itself: here they are
P = NP
1. Algorithmica: NP-complete problems can be solved in P, i.e. (deterministic) polynomial running time.
P ≠ NP
2. Heuristica: NP-complete problems are easy on the average case and hard on the worst case.
3. Pessiland: NP-complete problems are hard on the average case and one way functions do not exist. Generating hard instances of NP-complete problems are not possible. Worst of the five worlds, because we cannot exploit the hardness of average case NP-complete problems to cryptographic advantage.
4. Minicrypt: One way functions exist but public key cryptography is not possible.
5. Cryptomania: Public key cryptography and secure communication are possible.

I believe that we are in Cryptomania, although it is open, it has not even been disproved about Algorithmica (P versus NP problem).

However, I do not understand in Minicrypt if one way functions exist why public key cryptography should be impossible.
And, I do not understand in Pessiland if NP-complete problems are hard on the average case, why generating hard instances should be impossible and why one way functions could not exist at all.

May be it is analogous to us not being able to visualize how formal languages that are not recursively enumerable will look like ??

Originally Posted by CRGreathouse

I'm not aware of any subexponential (exact) algorithms for set cover.

Should be a consequence / corollary of the unproven exponential time hypothesis (ETH) you mentioned above.

- HIGHLY CONFIDENTIAL -

Originally Posted by Batalov

This BS has got to stop.

BS means business?

Sure. After my long taken break, I will behave in a way that others will respect me, not like before. I think that I have good writing skills. I think that behaving in a way that others would respect me, is the most important. Otherwise some one would take advantage, and then lower down my reputation. See, before in OEIS, NJA Sloane lowered the limits of those guys / contributors who didn't act in such a way that other people would respect them.

No serious BS in my previous message / post. (By BS I know you meant bullshit).

"Thank you. -so- -so- -so- How old are you?" My previous message / post would have been fancier if it were -so- instead of -do-. "How old are you?" was a question I liked to ask but I did leave that with in white font colour because which due to the case for respecting privacy, I don't mind if it weren't replied to.

-do- means ditto, repeat the same line again. That is to skip away a given line (empty / blank one), i.e. to insert away a line break. It also means the normal -do- :

Originally Posted by Raman

If I - do - understand correctly, then even for NP-complete problems, most instances should be solvable with in (deterministic) polynomial running time.

- HIGHLY CONFIDENTIAL -

Originally Posted by jwaltos

CRGreathouse, you provided a very nice response within this post!
Because of the quality of the response I would like to solicit an opinion regarding the complexity class to which a general form of integer factorization will belong which I presume includes the integer form of complex values.

Did you mean "thread" rather than, instead of "post"?

Integer Factorization is in NP ∩ co-NP, and even UP ∩ co-UP. If factoring were not in P, this would imply P ≠ NP ∩ co-NP and P ≠ UP ∩ co-UP. Could they be true? We already have R = RE ∩ co-RE, only for an example certainly. The other important NP-intermediate problems are Discrete Logarithms (analogous to Integer Factorization !?) and Graph Isomorphism.

If Integer Factorization is NP-complete, then the polynomial hierarchy would collapse to its first level, i.e. NP = co-NP.
If Graph Isomorphism is NP-complete, then the polynomial hierarchy would collapse to its second level, i.e. NP^NP = co-NP^NP.

Shor's algorithm can solve both the Integer Factorization and the Discrete Logarithm problem with in (quantum) polynomial running time. So, they both are in BQP.

It is open that whether one of these three important NP-intermediate problems: Integer Factorization, Discrete Logarithms, Graph Isomorphism can be in P. For example, it wasn't known that primality testing was in P until the AKS algorithm of 2002. So, it could be possible that one of these three important NP-intermediate problems can be in P. Primality testing was long known to be in BPP, the Fermat's Little Theorem / the Rabin Miller's test gives away an initial excellent idea for most of the numbers, with false positive chances being less than one in a billion, with that probability being decreasing away as the size of the candidate numbers being increasing away. In turn, it could be possible that P = BPP and problems like Polynomial Identity Testing is known to be in BPP but not P. It should be very certainly be in P. Only in 2004, it had been proven that L = SL, which is being with an algorithm in L for the problem of undirected graph reachability from one vertex to another, i.e. for the problem of undirected graph s-t connectivity.

Could Graph Isomorphism be in BQP? Is Graph Isomorphism easier or harder than Integer Factorization / Discrete Logarithms? The polynomial hierarchy collapse to its first level, i.e. NP = co-NP for Integer Factorization and the polynomial hierarchy collapse to its second level, i.e. NP^NP = co-NP^NP for Graph Isomorphism seems to suggest that Graph Isomorphism is harder than Integer Factorization / Discrete Logarithms. How could the complexity class BQP not include all problems from NP, for example the NP-complete problems, but include some problems outside NP that which are being with in PSPACE ??

I will follow up with in further more ideas about it here, with in the future, only certainly during at @ a later date. Further more with in much others with in the process of preparation. Further more with in much others with in the process of working out.

Every where (bit) should have been (bit wise).

[ET_]

...he did it again...

[CRGreathouse]

Originally Posted by Raman

Hello, I just quoted a statement from Wikipedia: Common misconceptions about NP-completeness, like
1. For NP-complete problems, most instances can be solved in P.
2. For NP-complete problems, we have algorithms that run in superpolynomial time or subexponential time.
3. NP-complete problems are not the hardest problems, some algorithms need more than (deterministic) exponential running time or are undecidable (the complexity classes PSPACE / EXPTIME / ... exist).
4. Breaking some cryptographic ciphers like AES and DES is in P, but with the large constant in its complexity, running time required to break it will exceed the age of the universe.
5. NP-complete problems can be solved in P under some special cases.

So, you are claiming that Wikipedia is wrong or needs corrections ?!

Give me the quote and a link to the article and I'll tell you.

Originally Posted by Raman

By the way, I have studied about Impagliazzo's Five Worlds before itself: here they are
P = NP
1. Algorithmica: NP-complete problems can be solved in P, i.e. (deterministic) polynomial running time.
P ≠ NP
2. Heuristica: NP-complete problems are easy on the average case and hard on the worst case.
3. Pessiland: NP-complete problems are hard on the average case and one way functions do not exist. Generating hard instances of NP-complete problems are not possible. Worst of the five worlds, because we cannot exploit the hardness of average case NP-complete problems to cryptographic advantage.
4. Minicrypt: One way functions exist but public key cryptography is not possible.
5. Cryptomania: Public key cryptography and secure communication are possible.

Actually Algorithmica is larger than that -- it includes, for example, the case where P ≠ ZPP = NP.

Originally Posted by Raman

I believe that we are in Cryptomania, although it is open, it has not even been disproved about Algorithmica (P versus NP problem).

Yes, I had mentioned that.

Originally Posted by Raman

However, I do not understand in Minicrypt if one way functions exist why public key cryptography should be impossible.

You misunderstand -- that's not a consequence of one-way functions but merely the definition of minicrypt. The reason it fits into the world hierarchy is that you could (a priori) have one-way functions without having public-key crypto, but you can't have public-key crypto without one-way functions.

Originally Posted by Raman

Should be a consequence / corollary of the unproven exponential time hypothesis (ETH) you mentioned above.

It's not obvious to me that this is true. I'd have to see what kind of reductions there are between set cover and SAT.

Originally Posted by Raman

Integer Factorization is in NP ∩ co-NP, and even UP ∩ co-UP. If factoring were not in P, this would imply P ≠ NP ∩ co-NP and P ≠ UP ∩ co-UP. Could they be true? The other important NP-intermediate problems are Discrete Logarithms (analogous to Integer Factorization !?) and Graph Isomorphism.

Yes, discrete log is 'basically the same' as factorization and usually an improvement in one applies to the other.

I wouldn't use GI as an example of NP-intermediate; I think the consensus is that it's probably in P. Last year László Babai gave an algorithm for solving it in exp(log(n)^O(1)) which is very close to being polynomial. For contrast the best algorithm for factorization is exp(O(n^(1/3) (log n)^(2/3))) which is very much larger. (For both n is the number of bits in the input.)

Originally Posted by Raman

If Graph Isomorphism is NP-complete, then the polynomial hierarchy would collapse to its second level, i.e. NP^NP = co-NP^NP.

If GI were NP-complete all hell would break loose.

Originally Posted by Raman

In turn, it could be possible that P = BPP and problems like Polynomial Identity Testing is known to be in BPP but not P.

That is, polynomial identity testing is not known to be in P.

P =? BPP is wide open as far as I know. Scott Aaronson is on record as saying he thinks they're the same.

Originally Posted by Raman

Could Graph Isomorphism be in BQP?

Probably. Gaitan & Clark gave a quantum algorithm, and probably it could be improved by using Babai's result (which is more a characterization of 'hard' instances of GI than an algorithm per se).

Originally Posted by Raman

Is Graph Isomorphism easier or harder than Integer Factorization / Discrete Logarithms?

GI is vastly easier than factorization.

Originally Posted by Raman

How could the complexity class BQP not include all problems from NP, for example the NP-complete problems, but include some problems outside NP that which are being with in PSPACE ?

What's the difficulty? I think it's widely believed that BQP is not in NP and NP is not in BQP. Expecting containment is tantamount to expecting quantum computers to work just like (possibly more powerful) conventional computers. But they're not -- they work really well for certain problems, but not at all for others. For example, consider Holevo's theorem: to store n bits of information requires n qubits; using fewer is no better than recording the first few and guessing the missing bits.

[jwaltos]

Thanks CR.

Many years ago when I first encountered Euler's solution to Bernoulli's inverse square sum I tried
solving it (fruitlessly) for about a month before I threw in the towel (and my ego) and read the
solution. Awe is an apt word for what I subsequently studied and I can humbly only echo Laplace.

Turing apparently, when encountering an interesting question that was solved, would not look at the
solution but would prefer to solve it himself.

Cultivating an ability to focus on the diaphanous and ephemerous, that is, looking at all of the
pieces which may or may not be part of that specific puzzle you are looking at (using a wrench for
a hammer is part of this approach) and suddenly noticing something that brings everything into
perspective thus providing a tangible insight or approach to understanding is very, very very
hard work. This is thinking from the inside outwards rather than from the outside in and either
you are gifted and see/assimilate rapidly and clearly or like myself, you trudge through the jungle,
lost, second guessing yourself, making mistakes and putting your trust in that compass of logic
that will lead you to somewhere you haven't been knowing that you are not going in circles (tautologies).
I recommend Wittgenstein's Tractatus and Investigations for those who have not yet encountered them.


For those who think in demarcations of classical and quantum, what's beyond? Cajori's tome on
notation is worth the read. Invention, utility and evolution is one thing I got out of it. Unfortunately
there is no such thing as a `mathematical esperanto.`

Anyways, that's my (tired) tirade for the day, my apologies.

Regarding the IFP, in addition to the above, part of my kitchen sink approach involves the heavy use of
pen and paper (but no eraser) and sophisticated hardware/software of the arcane and COTS variety.

[CRGreathouse]

Originally Posted by jwaltos

For those who think in demarcations of classical and quantum, what's beyond?

Scott Aaronson has studied some problems along these lines. An interest of his is seeing what modifications could be made to quantum mechanics to make it more or less powerful.

He defines DQP as BQP with access to the history of hidden variables and shows that it is stronger, but only slightly stronger, than BQP. For example, a Grover search takes x^1/3 rather than x^1/2.

He defines PostBQP which is polytime quantum computation with postselection, where he shows that it 'blows up' to all of PP (a very powerful class containing MA which itself contains NP).

He proves that adding closed timelike curves (a particular form of time travel) to BQP gives PSPACE (which is also huge, containing the entire polynomial hierarchy).

Recently he published a paper defining PDQP (BQP with non-collapsing measurements) which contains BQP and conjecturally does not contain NP.

Originally Posted by jwaltos

Cajori's tome on
notation is worth the read.

I assume this is
https://archive.org/details/historyofmathema031756mbp
?

[LaurV]

Originally Posted by CRGreathouse

Actually Algorithmica is larger than that -- it includes, for example, the case where P ≠ ZPP = NP.

I think that is more or less in Heuristica. If P=NP, there can be nothing in between. This stuff with ZPP, ZPL, RP, RL, or even UP and RE, generally all that include "randomized", are all in Heuristica. Of course, I may be wrong here, my last touch with it was years ago, and that also depends of how much weight one puts on the "randomized" part (i.e. is that a well defined function which works with random variables, or it is a random function, or a complete magic hat from which we pull a solution?).

[CRGreathouse]

Originally Posted by LaurV

If P=NP, there can be nothing in between.

Agreed. But Algorithmica includes not only P = NP; Impagliazzo defined it as follows:

Algorithmica is the world in which or some moral equivalent, e.g.,

Originally Posted by LaurV

that also depends of how much weight one puts on the "randomized" part (i.e. is that a well defined function which works with random variables, or it is a random function, or a complete magic hat from which we pull a solution?).

At this point it's probably best to break out the definitions. Each of these definitions concerns decision problems: given a finite string of bits, return "yes" or "no". (Some allow alternate answers like "maybe".)

P (polynomial time) is the class of decision problems solvable in polynomial time, i.e., problems with algorithms such that there is a polynomial f(x) such that, given an input with n bits, it finds a solution in at most f(n) steps.

BPP (bounded-error probabilistic polynomial time) is the class of decision problems which can be 'solved' in polynomial time and which give the correct result with probability >= 2/3.

Theorem: If "2/3" is replaced with any number larger than 1/2 in the definition above, the class is unchanged.

RP (randomized polynomial time) is the class of decision problems which can be 'solved' in polynomial time and which give the correct result with probability 1 if the correct answer is "no" and at least 1/2 if the correct answer is "yes". co-RP is the same thing with "yes" and "no" reversed.

Theorem: If "1/2" is replaced with any number larger than 0 in the definition above, the class is unchanged.

ZPP (zero-error probabilistic polynomial time) is the class of decision problems which can be solved in polynomial time and may answer "maybe" with probability at most 1/2 (and must otherwise give the correct answer).

Theorem: If "1/2" is replaced with any number smaller than 1 in the definition above, the class is unchanged.

Theorem: An equivalent definition for ZPP is the class of decision problems with can be solved (without using "maybe") in expected polynomial time for each input. Edit: that is, there is a fixed polynomial f(x) such that the expected runtime for each n-bit input is at most f(n) -- you don't get to switch polynomials. :)



I won't define the others here (BQP and PP are somewhat tricky) but suffice it to say that PP, PSPACE, and EXP are considered impractical while P, ZPP, RP, co-RP, and BPP are considered practical. The jury's still out on BQP (bounded error quantum polynomial time).

[jwaltos]

The Dover edition contains both volumes and can be gotten second hand as well..

Aaronson`s blog is a good and there are a few others of that quality that are obtainable through academic links.

[Raman]

Originally Posted by ET_

...he did it again...

??

Please quote what I did it again, if you would dare to reveal it out to me it.

[COLOR="White"]at all @.Certainly he had asked me only to stop the bullshit / business messages / text
Not - not the highly confidential hidden messages / text with in the white colour font / spoiler tag / strike through tag / tiny font size / LaTeX tag / TeX tag at all [COLOR="white"]@.[/COLOR]

My latest message / text had not - not at all [COLOR="white"]@[/COLOR] the bullshit / business messages / text at all [COLOR="white"]@.[/COLOR]
Only certainly [COLOR="white"]at all @.[/COLOR]

My latest messages / texts might contain with in the highly confidential hidden messages / text from time to time [COLOR="white"]at all @.[/COLOR]
Not - not necessarily / sufficiently with in the white colour font / spoiler tag / strike through tag / tiny font size / LaTeX tag / TeX tag at all [COLOR="white"]@.[/COLOR][/COLOR]

Originally Posted by CRGreathouse

Give me the quote and a link to the article and I'll tell you.

Just the Wikipedia article on NP-completeness !!

Originally Posted by Wikipedia

Common misconceptions
The following misconceptions are frequent.

"NP-complete problems are the most difficult known problems." Since NP-complete problems are in NP, their running time is at most exponential. However, some problems provably require more time, for example Presburger arithmetic.
"NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example minimum spanning tree). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see Valiant–Vazirani theorem).
"Solving NP-complete problems requires exponential time." First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time such as O(2^√nn). For example, the Independent set and Dominating set problems are NP-complete when restricted to planar graphs, but can be solved in subexponential time on planar graphs using the planar separator theorem.
"All instances of an NP-complete problem are difficult." Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.
"If P=NP, all cryptographic ciphers can be broken." A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. For example, ciphers with a fixed key length, such as Advanced Encryption Standard, can all be broken in constant time (and are thus already in P), though with current technology that constant may exceed the age of the universe.

at all [COLOR="White"]@ !?. By using be being.Missed out quoting the any / some latest additions to my previous post ??
"We already have R = RE ∩ co-RE, only for an example certainly" and then "Every where (bit) should have been (bit wise)".
This seems to suggest that you would surely use the offline text editor to compose replies, not the online web browser to compose replies.

Using lighter colours - cyan, green, yellow, gray to text which does not require replies / which does not stay there by appropriately.
Using darker colours - red, blue, magenta, orange to text which does stay there by appropriately / which does require replies.
Using lighter colours - white to avoid distracted text.
Using darker colours - black for normal text.

Colour, colour what colour do you choose.
And then enjoying playing with in this any / some very game / sport / puzzle variably there by seriously / jokingly - not - not
Each symbol ?? / ? / ?! / !? / ! / !! has got its own meaning with in my own latest messages / texts similarly to that of chess / / / / / / ?!.[/COLOR]

Originally Posted by CRGreathouse

Thanks!

Integer factorization is probably the most famous of the NP-intermediate class: in NP ("easy to check") but conjecturally outside P ("easy") and hence not NP-complete. The evidence that it's not NP-complete is compelling: if it were NP-complete that would imply the collapse of NP and co-NP ("easy to disprove") since AKS shows that primality is in P. The evidence that it is not in P is weaker, essentially our inability to find a fast algorithm. Still, the smart money is on NP-intermediate.

I don't think anyone thinks it's in RP ("easy with randomness").

It's also known to be in BQP ("easy with quantum computers") which probably ends up telling us more about the problem than any of the other classes.

So, where do you think that the AI-complete problems like Object Detection, Image Matching, Speech Recognition, Question and Answering, Natural Language Understanding, etc. would fit into the complexity classes hierarchy ??

Originally Posted by CRGreathouse

Actually Algorithmica is larger than that -- it includes, for example, the case where P ≠ ZPP = NP.

Yes, as LaurV did state up above, P ≠ ZPP = NP implies that P ≠ NP only certainly, which is surely out of Algorithmica world one of five classes, Impagliazzo's his own one of five equivalence classes.

Originally Posted by CRGreathouse

You misunderstand -- that's not a consequence of one-way functions but merely the definition of minicrypt. The reason it fits into the world hierarchy is that you could (a priori) have one-way functions without having public-key crypto, but you can't have public-key crypto without one-way functions.

So, you do mean it that I should need to imagine a world with in, i.e. meaning a universe in side which existence of one way functions does not necessarily imply that public key cryptography is being always possible.
Oh, I do see it sufficiently !!
A world with in which silicon-based life forms exists, rather than instead of carbon-based life forms,
or arsenate backbone for DNA double helix structure, rather than instead of phospate backbone for DNA double helix structure,
or methane (CH₄) based lower temperature oceans, rather than instead of water (H₂O) based higher temperature oceans, as with in in side of the scenario for Saturn's own moon of Titan.
Oops, sorry !! that all the above statements as stated up are being true with in in side of our own universe.
May be meaning a scenario with in in side of which quarks, leptons, photons, gluons, W / Z / Higgs bosons are not the building blocks of matter / anti-matter.
May be meaning a scenario with in in side of which the strength of gravitational force / electromagnetic force / strong nuclear force / weak nuclear force / frictional force / fifth force are all being different.
Or our own universe would may be topple into a false vacuum state / vacuum decay / through quantum fluctuations process / mechanism for an example only certainly - sake / purpose - surely.

[CRGreathouse]

Originally Posted by Raman

Just the Wikipedia article on NP-completeness

On review, the Wikipedia article seems fine -- it was just your summary "even for NP-complete problems, most instances should be solvable with in (deterministic) polynomial running time" which was wrong.

Originally Posted by Raman

Using lighter colours - cyan, green, yellow, gray to text which does not require replies / which does not stay there by appropriately.
Using darker colours - red, blue, magenta, orange to text which does stay there by appropriately / which does require replies.
Using lighter colours - white to avoid distracted text.
Using darker colours - black for normal text.

This makes your post hard to read -- please don't do this.

Originally Posted by Raman

So, where do you think that the AI-complete problems like Object Detection, Image Matching, Speech Recognition, Question and Answering, Natural Language Understanding, etc. would fit into the complexity classes hierarchy ?

They're not sufficiently well-defined to fall into any of the complexity classes. (What does it mean to wreck a nice beach? )

Originally Posted by Raman

Yes, as LaurV did state up above, P ≠ ZPP = NP implies that P ≠ NP only certainly, which is surely out of Algorithmica world one of five classes, Impagliazzo's his own one of five equivalence classes.

P ≠ ZPP = NP (which obviously implies P ≠ NP) is in Algorithmica, not Heuristica. Re-read Impagliazzo, or at least read his quote in my earlier post.