Cumulative General Science/Technology Quiz

[Serutan]

Niklas is right. His question.

@Abaddon - I think it's just because it's one thread for all the questions.

 

[Niklas]

Alright, time to switch science discipline:

What does it mean for a problem to be NP complete?

 

[dutchfire]

Something with the amount of time it takes to solve or something. NP complete means that it's linear IIRC. I once read about it, but forgot

 

[Niklas]

At least you got the general area of the question right. But your answer is more or less as wrong as it could be.

 

[Mise]

Guess based on vague memory of a wiki article on sorting algorithms I once read... "NP complete means that it's a problem that can't be solved in polynomial time"? i.e. time taken ~ not O(n^a), but O(a^n), where n is the number of "units" to be computed (e.g. number of items to be sorted) and a is some arbitrary constant?

 

[Niklas]

Now you've got the NP part (NP = non-polynomial), but not the NP complete part. Though that might be a bit too difficult, so if no one gets it soon I'll give you the floor.

 

[Mise]

(don't give me the floor if no-one else gets it -- I'm rubbish at question setting! Erik Mesoy should get this one though... He seems up on all this NP crap.)

 

[Niklas]

Yeah, if Erik reads this he's going to know for sure.

 

[Aramazd]

Bacteria use peptidoglycan, fungi use chitin, plants use cellulose.

Correct , but I passed the floor a while ago.

 

[StarWorms]

Correct , but I passed the floor a while ago.

Next time leave it open a bit longer; in my timezone the question was open from 2am to 6am.

 

[Niklas]

Well, if no one gets my quiz correctly, and since Mise doesn't want the floor, I can always give it to StarWorms for managing Abgar's quiz correctly. Though I'll wait at least 24 hours from posting my quiz.

 

[dutchfire]

Well, if no one gets my quiz correctly, and since Mise doesn't want the floor, I can always give it to StarWorms for managing Abgar's quiz correctly. Though I'll wait at least 24 hours from posting my quiz.

I vaguely remember something about this in a wiki-article as well, I believe it's one of 7 great problems in math.

Is it that if you have the answer, it's "easy" to check if it's correct, but it's very hard to find the answer?

 

[Niklas]

You're getting closer.

It is one of the 7 great problems in math (well, 6 now that one has been solved), or rather, P=NP is. I.e. can NP problems actually be solved in polynomial time, thereby equating the two categories? Most everyone "knows" it isn't so, but no one has been able to prove it.

More formally, NP is the set of problems for which an answer can be verfied (as opposed to found) in polynomial time. P is the set of problems for which and answer can be found in polynomial time.

Meh, I can just as well give the answer since there seems to be no immediate takers:

An NP complete problem is one that all other NP problems can be expressed in terms of. That means that if one could prove the existance of a polynomial-time solution to one NP complete problem, all other NP problems could be expressed and thus solved in terms of that, proving that P=NP. Conversely, and more likely, if it could be proven for any one NP complete problem that there cannot exist a polynomial-time solution, that would also prove that P=/=NP.

dutchfire, Mise or StarWorms can go, whoever gets there first.

 

[StarWorms]

Which is the largest gene in the human genome?

 

[ori]

dystrophin

 

[StarWorms]

Correct, next question!

 

[ori]

I wanted to switch fields - but since I am pressed for time today, I go with my Avatar's job:

What was the first DNA Repair mechanism that was discovered?

 

[StarWorms]

Mismatch ?

 

[Niklas]

StarWorms, you have to wait one round before you may answer again...

As for the question, I have no idea.

 

[ori]

Mismatch ?

N o