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

[Batalov]

Originally Posted by Raman

??

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

Here's a google translate of an article that explains that one should not typeset their messages like that. TL;DR version of that article is that such typesetting clearly demonstrates only the writer's attitude of complete lack of giving a about readers - https://translate.google.com/transla...5B8&edit-text=

The view of an average reader is attached. The reader's eyes bleed from reading this.

[LaurV]

I think he was banned in the past once, for things like that. This is kinda trolling, but idiotic trolling, in the sense that a troll will want his futile rants to be read by as many people as possible, contrary to this one which seems he wants as many people as possible to skip reading his texts. Many users (me including) skipped the eyes-blinding fragments. So, he is losing here, as he won't get a reply from an authority in domain like me.

Re: P ≠ ZPP = NP, after reading the CRG's points and refs, that is enough "Algorithmica" for me.

[Raman]

Originally Posted by Raman

The optimization version of the set cover problem is NP-hard while the decision version of the set cover problem is NP-complete.

This means that if you have got a set cover of size ≤ k, then you can check out whether it is really a set cover of size ≤ k in (deterministic) polynomial time, but checking out whether it is the smallest (optimal) set cover takes (deterministic) exponential time. Devil !!
Taking some sense, completeness means solving that problem captures essentially solving all problems instances of that parent complexity class.
Grasping surely, for an example only certainly - if solving AI-complete problem instance of Question and Answering, then involves essentially solving all elements of Natural Language Understanding.

Originally Posted by CRGreathouse

GI is vastly easier than factorization.

Really? I thought that Integer Factorization / Discrete Logarithms is easier than Graph Isomorphism.
Because Integer Factorization / Discrete Logarithms is in co-NP.
(To disprove a number has no factor, we can use AKS primality test which is in P.
To disprove an equation g^x ≡ h (mod p) has got no solutions, we must check out that the group order of g (mod p) is a multiple of the group order of h (mod p)).
Is graph isomorphism in co-NP? I don't think so.
Or things have just been changed recently by the quasi-polynomial time algorithm of László Babai which was being given by him last year as you had been mentioning above?
Or are there problems in P which are not in co-NP ?? (Joke !!) If graph isomorphism were in P, it should be surely with in of in side complexity class of co-NP. Right ??

I assumed that Graph Isomorphism was not in co-NP. But I may be wrong.
If Graph Isomorphism were in co-NP, since it is already in NP, it would surely be in NP ∩ co-NP, like Integer Factorization / Discrete Logarithms. (What about graph isomorphism with relation to complexity classes of UP, co-UP and UP ∩ co-UP ??)
That means that if Graph Isomorphism were NP-complete, the polynomial hierarchy would collapse to the first level, i.e. NP = co-NP, like Integer Factorization / Discrete Logarithms.
But, with in reality that if Graph Isomorphism were NP-complete, the polynomial hierarchy would collapse only to the second level, i.e. NP^NP = co-NP^NP.
That means that Graph Isomorphism is only with in NP^NP ∩ co-NP^NP and not at all in NP ∩ co-NP or co-NP. So, Graph Isomorphism is with in reality that harder than Integer Factorization / Discrete Logarithms.
So that am I missing out some thing ??

The fact that if Graph Isomorphism were NP-complete,
the polynomial hierarchy collapse to the first level implies the polynomial hierarchy collapse to the second level,
or the polynomial hierarchy collapse to the second level implies the polynomial hierarchy collapse to the first level ??

Only that the latter statement would surely imply that Graph Isomorphism is easier than Integer Factorization / Discrete Logarithms.
Other wise that the former statement would surely imply that Integer Factorization / Discrete Logarithms is easier than Graph Isomorphism.

I assumed that the former statement was true.
Because
NP = co-NP implies that NP^NP = co-NP^NP.
A problem is in NP ∩ co-NP implies that this problem is in NP^NP ∩ co-NP^NP.

@ Not the other way around at all.

Originally Posted by Impagliazzo (April 17, 1995)

If an efficient way of factoring integers and solving discrete logarithms became known, then not only would the popular public key cryptosystems be broken, but there would be no candidate for a secure public key cryptosystem, or any real methodology for coming up with such a candidate.

Although it was written up on April 17, 1995, may be things have got changed with in time ??
Why would only Integer Factorization / Discrete Logarithm form the base of public key cryptosystems with in, could we not exploit the power of other NP-complete problems (most of which are graph problems) and other NP-intermediate problems (including Graph Isomorphism problem, if it were not in P, assuming that P ≠ NP).
By the way, elliptic curve cryptosystem is a good candidate with in, is elliptic curve discrete logarithm problem being in BQP ?? co-NP ?? NP ∩ co-NP ?? UP ?? co-UP ?? UP ∩ co-UP ?? NP ?? P ??

Originally Posted by CRGreathouse

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.

That means that my previous post with P = NP for Algorithmica and then P ≠ NP for Heuristica, Pessiland, Minicrypt, Cryptomania is being totally wrong all together - what ever has been got with in.
It should have been P = NP, P ≠ NP for Algorithmica including for an example NP BPP, P ≠ NP for Heuristica, Pessiland, Minicrypt, Cryptomania.

Originally Posted by CRGreathouse

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

- As with in as lighter font text -
Actually, highlighting text will make one to read out lighter colour font text easily.
Any way that I used out lighter colour font text only as for unimportant data and then any / some things and then stuffs with in my previous post.
As the human eye is most sensitive to green colour light (wavelength of 500 nanometers, with in core center of visible spectrum from 300 nanometers up to 700 nanometers down to), any font text colour combination or mixture that contains with in higher amounts of green colour pigment will appear as lighter colour font text - that is I meant that as lighter font text to the human eyes.

I also switched over to offline text editor to compose replies, etc. (etc. = End of thinking capacity !?) and then so on
so that - rather than instead of online web browser to compose replies
a while back, ago too !!

There were a few corrections with in my previous post
what ever that I do
should have been

Originally Posted by Raman

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, neutrinos, 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 true vacuum state / vacuum decay / through quantum fluctuations process / mechanism for an example only certainly - sake / purpose - surely.

I have stayed away from Mersenne Forum and OEIS for nearly 2½ years by now.
Spent much of my time circling through my Chennai city / town, including several half marathons (about 21.0975 kilometers of distance) to my relative's houses. (Cf. Fit Bit, Runtastic Android / iOS applications) - snip - Cf. means what actually - snip means what actually.
Full marathons (about 42.1950 kilometers of distance) will take 8½ hours at maximum speed of 5 kilometers per hour without taking food and water from shops and breaks in between without getting tired without taking naps in the scorching heat of sun and 10½ hours at minimum speed of 4 kilometers per hour with taking food and water from shops and breaks in between and taking naps in between to cool off to avoid getting tired from the scorching heat of the sun.
I am now working out at a software engineer job at with in Hyderabad (Secunderabad) city / town after finishing off my M.Phil degree program from Institute of Mathematical Sciences, Chennai city / town and then working out with in at a software engineer job at Chennai city / town for one year during time period frame duration.
Ph.D. degree program / Research paper publication degree program / PDF degree program (File will it open ?? Joke !!) - Post Doctoral Fellow ship degree program - I can do it in the future, when ever I want to, as a part time with software engineer job, or as a freelancer. By the way, only people who opt out for teaching profession will only do a Ph.D. degree - I have been noting up stairs to down stairs to - I have been noticing up stairs to down stairs to - my own.
Master's degree program is being needed / necessary / sufficient for a teaching profession - with in in side between need.
Is teaching profession being worth while? Simply teaching some thing to students with out producing or developing any thing by result by themselves. Personally, I would respect out a software engineer much further more than a teacher.
I will also respect people who will publish academic research papers too !! But, that research is always being unpredictable of producing or developing any thing by results by themselves.
Never to give up hopes at all @ during time period frame durations !! Not to expect any thing from me seriously with in a field that is being unpredictable at all @ during time period frame durations !!
If I do want to go with in some thing that I strictly want to, I will end up with nothing !! Not to lose out with in the other opportunities chances turns !!
I have got to take with in each opportunity chance turn seriously !! Not to wait for other people to teach !! I must learn by myself every thing as soon as possible !! Only then I can get away with in the most profit from the developmental stages !!
Limited opportunity / chance - before working out jobs do get automated - must / should consider working out jobs right from a young age.

[CRGreathouse]

Originally Posted by Raman

This means that if you have got a set cover of size ≤ k, then you can check out whether it is really a set cover of size ≤ k in (deterministic) polynomial time, but checking out whether it is the smallest (optimal) set cover takes (deterministic) exponential time. Devil !!

Not quite. The first part is right, but the NP-hardness of the optimization version just means that if you're able to optimize in time f(x), then you can solve any problem in NP with f(poly(x)) time. It doesn't mean that the optimization version requires exponential time (though it might).

In particular, the optimization version of set cover is in FNP which is not believed to majorize EXP.

Originally Posted by Raman

Really? I thought that Integer Factorization / Discrete Logarithms is easier than Graph Isomorphism.
Because Integer Factorization / Discrete Logarithms is in co-NP.
(To disprove a number has no factor, we can use AKS primality test which is in P.
To disprove an equation g^x ≡ h (mod p) has got no solutions, we must check out that the group order of g (mod p) is a multiple of the group order of h (mod p)).
Is graph isomorphism in co-NP? I don't think so.

Yes, Graph Isomorphism is in co-NP due to the theorems of Euclid and Pratt. Explicitly:

The decision version of factorization is: Given n and k, does n have a divisor d with 1 < d < k? It is in NP because if there is such a factor it is a proof that such a factor exists. It is in co-NP because if there is no such factor a proof is a complete factorization of n, plus a proof for each prime p in the factorization that p is prime. This relies on the fact that primality testing is in NP, as proved by Pratt and the fact that prime factorization in the integers is unique (due to Euclid).

Originally Posted by Raman

Or things have just been changed recently by the quasi-polynomial time algorithm of László Babai which was being given by him last year as you had been mentioning above?

No, the result predates Babai's by 40 years.

Originally Posted by Raman

What about graph isomorphism with relation to complexity classes of UP, co-UP and UP ∩ co-UP ?

I don't think this is known. If GI is not in P then there's no obvious way to show that it's in UP... but of course that doesn't mean there isn't one.

Originally Posted by Raman

So that am I missing out some thing ?

Yes... our level of knowledge of the collapse implied by something believed to be false isn't a good measure of how hard something is.

Originally Posted by Raman

Why would only Integer Factorization / Discrete Logarithm form the base of public key cryptosystems with in, could we not exploit the power of other NP-complete problems (most of which are graph problems) and other NP-intermediate problems (including Graph Isomorphism problem, if it were not in P, assuming that P ≠ NP).

There are plenty of other problems used; factorization is just the most common. Elliptic curve cryptography had been invented before the statement you quote but not really implemented yet. It's in common use now. (Sidenote: I certainly wouldn't say that most NP-complete problems are graph problems.)

Originally Posted by Raman

By the way, elliptic curve cryptosystem is a good candidate with in, is elliptic curve discrete logarithm problem being in BQP ?? co-NP ?? NP ∩ co-NP ?? UP ?? co-UP ?? UP ∩ co-UP ?? NP ?? P ??

This would be a good project for you to work out. I imagine all the answers not involving UP can be readily answered with Google and simple deduction.

Originally Posted by Raman

That means that my previous post with P = NP for Algorithmica and then P ≠ NP for Heuristica, Pessiland, Minicrypt, Cryptomania is being totally wrong all together - what ever has been got with in.
It should have been P = NP, P ≠ NP for Algorithmica including for an example NP BPP, P ≠ NP for Heuristica, Pessiland, Minicrypt, Cryptomania.

As a first cut you could take \(NP \subseteq BPP\) as a definition of Algorithmica, which subsumes P = NP as a possibility. I think Impagliazzo meant to include other unforseen possibilities as well -- perhaps there is some very small enlargement of P which includes NP, in which case he might consider us to be in Algorithmica even if BPP wasn't quite the right enlargement.

But yes, \(NP \subsetneq BPP\) is pretty much a requirement for Heuristica, Pessiland, Minicrypt, and Cryptomania.

Originally Posted by Raman

Actually, highlighting text will make one to read out lighter colour font text easily.
Any way that I used out lighter colour font text only as for unimportant data and then any / some things and then stuffs with in my previous post.

It's the inclusion of this extraneous data that's the problem, not its color. Although I find the color to make it worse, not better, because when replying to the post I have to wade through extra markup and when reading my attention is diverted by it, and all the more so if I have to pause to highlight it in case I do want to read it.

Edit: I think the attachments are an improvement.

[Raman]

Originally Posted by CRGreathouse

Yes, Graph Isomorphism is in co-NP due to the theorems of Euclid and Pratt. Explicitly:

The decision version of factorization is: Given n and k, does n have a divisor d with 1 < d < k? It is in NP because if there is such a factor it is a proof that such a factor exists. It is in co-NP because if there is no such factor a proof is a complete factorization of n, plus a proof for each prime p in the factorization that p is prime. This relies on the fact that primality testing is in NP, as proved by Pratt and the fact that prime factorization in the integers is unique (due to Euclid).

Is it possible that you are not concentrating properly upon what ever that you have been writing out?
You are mixing up the NP-intermediate problems of Graph Isomorphism and Integer Factorization.

Yes, Graph Isomorphism is in co-NP because ... reason Integer Factorization is in co-NP ?? What the hell !!

I am looking out why Graph Isomorphism is in co-NP, not Integer Factorization.
(I could even claim out that you had not concentrated properly upon what ever that you had been writing out when ever you stated that "Graph Isomorphism is being vastly easier than Integer Factorization").

Originally Posted by CRGreathouse

But yes, \(NP \subsetneq BPP\) is pretty much a requirement for Heuristica, Pessiland, Minicrypt, and Cryptomania.

You do meant that \(BPP \subsetneq NP\) ?? Tex tag usage = $ tag usage ??

But, why would it be called Pessiland? Any ideas? Any alternative names would be standing out appropriately ??

Originally Posted by Raman

/ quoted text data and then any / some things and then stuffs
/ temporary / non-permanent profession / occupation / structure / position / situation / location / condition / hobby / leisure at all @ during time period frame duration
I do meant as a separator - with in in side between out off - out off - I have been noting up stairs to down stairs to - I have been noticing up stairs to down stairs to - my own
/ temporary / non-permanent profession / occupation / structure / position / situation / location / condition / hobby / leisure at all @ during time period frame duration
/ quoted text data and then any / some things and then stuffs

When ever that some time before from 10000 character limit for mersenne forum posts had been raised to 16384 character limit for mersenne forum posts.

Limited opportunity / chance - before working out jobs do get automated - must / should consider working out jobs right from a young age.
→ Reputation / respect raising jobs
→ High technology jobs
→ Non-hazardous jobs / Non-dangerous / Non-risky / Safe / Non-unhealthy / Non-unhygenic / Non-immoral
→ Limited opportunity / chance jobs / temporary / non-permanent profession / occupation / structure / position / situation / location / condition / hobby / leisure at all @ during time period frame duration
→ Utilizing / proving talents jobs - "why do no body do recognize my own potential / potent / creativity innovation / skills concepts" - me (2002) - 14 years old

@ Godzilla - How old are you at all ??

lol - laughing out loud

I do wonder if there are any children / women doing participating / lurking over in this mersenne forum

Originally Posted by Raman

Spent much of my time circling through my Chennai city / town, including several half marathons (about 21.0975 kilometers of distance) to my relative's houses. (Cf. Fit Bit, Runtastic Android / iOS applications) - snip - Cf. means what actually - snip means what actually.
Full marathons (about 42.1950 kilometers of distance) will take 8½ hours at maximum speed of 5 kilometers per hour without taking food and water from shops and breaks in between without getting tired without taking naps in the scorching heat of sun and 10½ hours at minimum speed of 4 kilometers per hour with taking food and water from shops and breaks in between and taking naps in between to cool off to avoid getting tired from the scorching heat of the sun.

"Whether going out to / coming out from office / college / university / school / coaching tuition classes / sports puzzles games classes every day
It would be fun to try out different routes every day

Whether going out for / coming out for holiday / vacation
It would be fun to try out different places every day" - me (2016) - 28 years old

[chalsall]

Originally Posted by Raman

"It would be fun to try out different places every day" - me (2016) - 28 years old

Wow. To be in that brain.

[CRGreathouse]

Originally Posted by Raman

Is it possible that you are not concentrating properly upon what ever that you have been writing out?
You are mixing up the NP-intermediate problems of Graph Isomorphism and Integer Factorization.

Oops, sorry. Answering the wrong question there!

Hmm. Graph nonisomorphism is in SZK and hence AM. By a theorem of Miltersen & Vinodchandran, AM = NP on a (strong) derandomization hypothesis: some language in NE ∩ coNE requires SV-nondeterministic circuit complexity >> k^n for some k > 1, where (quoting the paper)

In an SV-nondeterministic circuit, there are two output bits, the real output bit, and a flag, indicating whether the computation has been correctly performed. On both positive and negative instances, if the flag is on, the output bit should be correct, and for all instances, there should be some setting of the nondeterministic choice bits that make the flag turn on.

Hence on this assumption GI is in co-NP. I don't know of an unconditional proof, does anyone else?

Originally Posted by Raman

You do meant that \(BPP \subsetneq NP\) ?? Tex tag usage = $ tag usage ?

I do not, I mean \(NP \subsetneq BPP\) (as expected). If \(NP \subseteq BPP\) then you're in Algorithmica.

[Raman]

Problem motivation:

I am looking forward planning right up to implement an Android Version of the Board Game "Cluedo" with more categories and more elements per category, and the first step is to implement an AI that will deduce the correct answer from the given set of suggestions made. This initial AI implementation does not need to roll the dice, go to each room to make a suggestion, but pick up one room at random within the suggestion.

Suppose we have some suggestions made by other players, say, and I know at least one of these three cards within each of these following suggestions is with Peacock. I will take a note of them during other player's turns.
(A) Lounge, Plum, Candlestick -> shown by Peacock
(B) Lounge, Mustard, Rope -> shown by Peacock
(C) Conservatory, Peacock, Revolver -> shown by Peacock
(D) Lounge, Plum, Revolver -> shown by Peacock
(E) Hall, Plum, Revolver -> shown by Peacock

For each card, let me associate the corresponding sets to which they belong to.
{Lounge, Conservatory, Hall, Rope, Candlestick, Revolver, Mustard, Peacock, Plum}
{ABD, C, E, B, A, CDE, B, C, ADE}
I am interested in the size of the smallest subset that contains all elements. Why? Let us suppose, if there are 6 players within the original "Cluedo" game version containing 21 cards and 3 categories, then each player will receive 3 cards. If you include a card (element of the given set) such that you would need at least 4 or more elements to form a subset of the given set that contains all elements (along with this element of the given set), then you can eliminate that this card (element of the given set) as not being with this corresponding player. Similarly, if you would include a card (element of the given set) and can form a subset of the given set containing all elements with 3 or less elements, and all subsets of the given set without this corresponding card (element of the given set) would require 4 or more elements to contain all elements, then we can conclude that this card (element of the given set) as being with this corresponding player.

Not sure if this one algorithm will do, but initially it would certainly be interesting to work out upon an Android application that which I am certainly most excited about, at all right at the first place.

As we can see, from within our sets, the total number of times each element appears remains fixed, and is equal to the total number of categories within the following sets made only.

(If there are N players within a variation of the "Cluedo" game version containing x cards and y categories, then N-((x-y) mod N) players will receive floor((x-y)/N) cards and (x-y) mod N players will receive floor((x-y)/N)+1 cards). At the beginning of the game, initially, I do know what players has got how many cards distributed to each player only certainly.

So, the core problem statement is only certainly,
Given a set of N elements, find out the size of the smallest subset that contains all elements.

If you do represent each element of the given set by one bit (different elements of the given set by different bits), then certainly the problem statement only reduces to
Given a set of N integers, find out the size of the smallest subset such that their (bit) OR is 2^(Total number of bits (elements of the given set) used)-1.

If you do take the 1's complement of these given integers, and then do replace within (bit) OR by using (bit) AND, then certainly the problem statement only reduces to
Given a set of N integers, find out the size of the smallest subset such that their (bit) AND is 0.