Re:This is an incorrect definition of NP
on
Does P = NP?
·
· Score: 3
Quoting Introduction to the theory of computation by Michael Sipser:
Section 7.3:
------------
THE P VERSUS NP QUESTION
As we have been saying, NP is the class of languages that are solvable in polynomial time on a nondeterministic Turing machine, or, equivalently, it is the class of languages whereby membership can be tested in polynomial time.
[...]
P = the set of languages where membership can be decided quickly
NP = the set of languages where membership can be verified quickly
[...]
----- end of quote -----
Actually, his definition of NP is:
------------
DEFINITION 7.16:
NP is the class of languages that have polynomial time verifiers.
----- end of quote -----
Finding if a graph has an hamiltonian path is NP complete, but to verify that the path [x] is an hamiltonian path can be done in polynomial time (finding if the path goes through every node exactly once...)
If we were in the 80's, it would be true... computers were costly and less useful to most people. But in 2000, people should consider investing in a computer... and they do. Why pay for a console, then? I mean, if you got the money for both, the question is pointless... and the parent message's first argument is also pointless. And don't forget that these consoles and these games aren't cheap.
For the second argument, "the number of consoles out there", i'm sorry, but most of these consoles 'out there' are not those which will be targeted for massively multiplayer games...
Finally, since hardcore gamers (people who care THAT MUCH about massively multiplayer games - not like my sister that likes Mario or my other friend who is happy with his Golden Eye the way it is) often play on a PC and are the majority of people who would pay a montly fee, i don't see why consoles would see a 'massive boom' in participation compared to mmg on the pc.
(be nice with me, as english is not my first language) phobos% cat.sig
Asking for 192MB ram for basic hassle-free use of a desktop computer seems pretty much to me. Before, computer geeks were fond of backward compatibility and reuse of hardware/software. Now, it seems that Mr. Everybody should buy a new computer every 2 years.
Well, i got great news... it is not in Mr. Everybody's habits to buy a 1500$ piece of hardware every 2 years (not a new piece that makes something else, but a piece of hardware they will do almost the "same" thing with). Yes, backward compatibility draws back tech. But no backward compatibility draws back the wide acceptance of tech.
Compact disks are quite old, but they are still in use and will be for quite some time... people still use walkmans and tape decks... etc. etc.
Reading about the new Mac OS X made me interested in it... and i am still interested... but I think that there are many good points in the article and it didn't feel to me like it was a pissed off 7 years old that wrote it.
The only person who can assure quality is a third party (Non developer), who does a full QA test on it. Trust me on this one.
QA testers are really useful (read: necessary) as they use systematic methods for the tests and have a fresh look on the project, but quality not only happening when the software goes through tests or walkthroughs.
Quality is good docs, "tested" analysis (the software is up to specs, but are the specs up to the needs of the customer?), and many other really important things... See any software engineering 101 course...
"The only person who can assure quality is a third party (Non developer)" is false... since for many (not all, and not the majority) quality assurance steps the developper is the right person to do his part of the job.
I don't know why I answer to this post, because actually, the biggest mistake was in the slashdot article: "The best person to assure quality is the developer"... This is oh soooo false.
I read some parts of it. Actually, i read one part, then click on a link to the same page, read another part, and there are contradictions. I don't mean that the author is not serious, but he doesn't seem that much objective. Example: he says that all decoders do the same things, but winamp got artefacts, and right under, there is an update saying that only winamp and 2 other players render perfectly mp3 files.
Anyways, i do honestly believe that there is a difference (you asked me), but I can be wrong. My computer is not plugged in my best amp (which i use more often), i do listen sometimes to cds on my computer (using the same amp) and for some types of music (crisp ambiant music - eg aphex twin - and classical music) it just doesn't feel the same.
As I said, i don't believe a hard drive is portable (in the same sense as a cassette player and a new discman are).
A MP3 device with 80Gb+ that is used for rips of cds you own with the output redirected to your stereo system is only more useful than a Pioneer 100-disk changer... if you are deaf.
I mean, who would want to downgrade the quality of the cds he paid for. Maybe if it was a.wav player...
I have nothing against this player (is it really that portable? how much can i carry my 20gig WD ide drive in my backpack without breaking it?) but mp3 is not lossless compression.
I am not an expert on the subject, but i have always felt that the potential for overclocking was what the margin between the maximum working speed of the chip - this is known by the company (Intel, Amd, etc.) - and the speed at which the chip is running "comfortably".
I have always wondered if a company A could make a chip with the same performance as company B, but send it out on the market at 100mhz faster than it's rival. (which would then be compared in price with company B's faster chip)
I mean, if the "safety margin" is subjective and there are no standards, how can i compare company A and B's chips?
And when AMD removes it's multiplier, how can i know if it is because:
1) they are loosing money on overclockers - really?
2) they are pushing a bit too much on their new chips and don't wan't people to notice their "safety margin" is smaller?
Actually, I don't know that much in hardware, so I could be totally wrong. Correct me if necessary...
No, i don't always follow links.
No, i don't want to bookmark every site i visit.
No, i won't go to the site if i can't type it's address.
What if they decide to host an english section?
These addresses would be limited to small communities sites and would not help the fact that you have the opportunity to reach a gobal public as you said.
Actually, modern desktop computers all share a common character set: ASCII. Let's use it. Actually, this address is only an easier thing to remember than a numerical IP (XXX.XXX.XXX.XXX)...
Information from Other Sources
For reasons such as improving personalization of our service (for example, providing better product recommendations or special offers that we think will interest you), we might receive information about you from other sources and add it to our account information. We also sometimes receive updated delivery and address information from our shippers or other sources so that we can correct our records and deliver your next purchase or communication more easily.
{...} What Choices Do I Have?
{...}
Click here to explore products that offer anonymous browsing. In addition, the Federal Trade Commission provides useful information about online privacy on its own Web site, Site Seeing on the Internet.
Dear customer,
We are building a large distributed database of your personal information. This information can get out of our hands at any time so, to ensure that other companies get the right information, we will even update it automagically by sharing info between our "circle-of-friend-companies-we-trust-and-you-can-a lso-trust-cause-they-are-pretty-and-love -flowers-and-all" and using high-tech heuristics to be sure we know precisly where you live and if you wear boxers of briefs.
What Choices Do I Have?
Actually, you need a big and complex piece of software whose only goal is to guard you from big companies like us. We sure hope it's got better heuristics than ours. Actually, it's a big game! You try to hide your info, and we try to get it! If we win, you don't know, but if you do win, you may get a prize!
Dear sir ~MegamanX~, this is Joe from Amazone. You won a car in the privacy contest. Could you give us your address so we can ship it to you. Check here if you want to receive emails of our special offers...
There's nothing I hate more than a standards body that doesn't have the foresight to avoid implementing names and processes they're going to completely drop further down the road (*hint* Java *hint*)
Everybody knows it's much better to:
Never redesign anything. Never evoluate.
Always keep backward compatibility since a standard is really usefull when there are 10 ways to do the same thing. It is so much cleaner.
We should all realize Java is heading the wrong way...
From the article: The count parameter is always set to the value 1 by the calling code. The byte read from the file descriptor fd into the RandBuf buffer is subsequently overwritten with the read() function's return value, which will be 1. The actual random data are not used.
If you have a legitimate reason to look at youngass.jpg, then surely you don't care if you are singled out and perhaps emailed by the server admin asking why you are requesting that file.
Come on... this is suuuch a false statement.
I am NOT a racist, but i WOULD care if someone wrote on a big wall that i was one... come on...
Even if you and your wife/children/parents know that you aren't a pedophile, would you like it if someone "proved" it and people started acting funny around you, talked in your back, etc??? Even if there is only a tiny possiblilty that people around you hear about it? No, you wouldn't like it. Even if you know that probably nobody you know will trace you, there is a doubt.
I'm sorry to say that, but I think you should get a life.
Makes me laugh how some people here think they are The Omniscient Wise Guy That Rules The Internet.
Thus France suffers from high unemployment and a lack of capital for new business start ups. When is the last time you bought anything that said "Made in France." Yes, I just bought an Airbus and plenty of other examples yesterday, but you wouldn't believe me.
Everybody in france is poor, sad and sick. It probably is because they don't do as you expect them to do, as they should do (== as the US do). They will never do anything good in software developpement and in any science. I think they are on the road to become bankrupt by the end of next year. (feel the irony)
Look at the subject of your post, damnit! Doesn't it sound stupid and "prétentieux" to you?????? You just made my day...
(Sorry for my english, my first language is french (i'm from Québec)...) phobos% cat.sig
But as you can see, it still is not enough for them... They have better eyes than me. 'cause i never saw the difference between 89fps and 113fps... but i can see one between 640x480 and 1600x1200... anyways... next time 3dfx will know what to do. Just remove visual features and give them 600fps 640x480... Maybe they also should slack on their Linux support too.
(the usual flaimbait here, i have to do it: seems that it doesn't work quite right with Athlons... and i just read an article about incompatibilities between Athlons and GeForces... and Athlons and memory, motherboards, etc... If I overclocked my coppermine and my voodoo, i swear i would do better in stability, compatibility and speed than you all with your "factory overclocked" Athlons+nVidea...;)
If we could "Print Screen", it would mean that the data is not encrypted in video memory. Since we got computers(!), i believe it would be a bit simpler to read the video memory (emulate a keypress on "print screen" if you wish) between every frame. And this would be no problem.
But if they are smart, data will be encrypted all the time up to when it reaches the chip in the monitor.
All the Windoze people have to say is, "Great. Now let's try the same thing on six new identical machines with redundant power supplies and drive arrays, just like you would do with a critical server in the real world."
I don't know, but would we be testing the redundancy mechanism more than the OS in that case? I understand that 2 computers are a relatively small sample (!), but as long as both computers had about the same hardware, you'll have to admit that NT was really not lucky;)
As for the redundancy, wouldn't it hide most of the OS problems? I mean... Micosoft's www site did not go down for some time, does that mean that windoze NT is really reliable or that a ~= 350 servers farm is enough to hide faulty servers?
Maybe with a more reliable OS companies would need less redundancy...
(I have no.sig and english is not my first language, but i'm still a good guy;) phobos% cat.sig
The CS department also made the move from IRIX to Linux (!) when they bought a big number of new Intel based stations. And here, everything has always been done on *nix systems. The support is not incredible here either... but it's understandable, i think. CS students should be able to install and configure a Linux distro by themselves (i mean get the info without the help of a support team... they should be able to use the Internet, shouldn't they? shouldn't they??;) Another way to work is also to work at school... or from a telnet terminal in a win32 environnement (!). There are no reasons why universities shouldn't use a free and stable operating system like Linux. -MegamanX phobos% cat.sig
Slashdot Mirror
Quoting Introduction to the theory of computation by Michael Sipser:
.sig
Section 7.3:
------------
THE P VERSUS NP QUESTION
As we have been saying, NP is the class of languages that are solvable in polynomial time on a nondeterministic Turing machine, or, equivalently, it is the class of languages whereby membership can be tested in polynomial time.
[...]
P = the set of languages where membership can be decided quickly
NP = the set of languages where membership can be verified quickly
[...]
----- end of quote -----
Actually, his definition of NP is:
------------
DEFINITION 7.16: NP is the class of languages that have polynomial time verifiers.
----- end of quote -----
Finding if a graph has an hamiltonian path is NP complete, but to verify that the path [x] is an hamiltonian path can be done in polynomial time (finding if the path goes through every node exactly once...)
phobos% cat
This comment isn't that much insightful.
.sig
If we were in the 80's, it would be true... computers were costly and less useful to most people. But in 2000, people should consider investing in a computer... and they do. Why pay for a console, then? I mean, if you got the money for both, the question is pointless... and the parent message's first argument is also pointless. And don't forget that these consoles and these games aren't cheap.
For the second argument, "the number of consoles out there", i'm sorry, but most of these consoles 'out there' are not those which will be targeted for massively multiplayer games...
Finally, since hardcore gamers (people who care THAT MUCH about massively multiplayer games - not like my sister that likes Mario or my other friend who is happy with his Golden Eye the way it is) often play on a PC and are the majority of people who would pay a montly fee, i don't see why consoles would see a 'massive boom' in participation compared to mmg on the pc.
(be nice with me, as english is not my first language)
phobos% cat
Asking for 192MB ram for basic hassle-free use of a desktop computer seems pretty much to me. Before, computer geeks were fond of backward compatibility and reuse of hardware/software. Now, it seems that Mr. Everybody should buy a new computer every 2 years.
.sig
Well, i got great news... it is not in Mr. Everybody's habits to buy a 1500$ piece of hardware every 2 years (not a new piece that makes something else, but a piece of hardware they will do almost the "same" thing with). Yes, backward compatibility draws back tech. But no backward compatibility draws back the wide acceptance of tech.
Compact disks are quite old, but they are still in use and will be for quite some time... people still use walkmans and tape decks... etc. etc.
Reading about the new Mac OS X made me interested in it... and i am still interested... but I think that there are many good points in the article and it didn't feel to me like it was a pissed off 7 years old that wrote it.
phobos% cat
The only person who can assure quality is a third party (Non developer), who does a full QA test on it. Trust me on this one.
.sig
QA testers are really useful (read: necessary) as they use systematic methods for the tests and have a fresh look on the project, but quality not only happening when the software goes through tests or walkthroughs.
Quality is good docs, "tested" analysis (the software is up to specs, but are the specs up to the needs of the customer?), and many other really important things... See any software engineering 101 course...
"The only person who can assure quality is a third party (Non developer)" is false... since for many (not all, and not the majority) quality assurance steps the developper is the right person to do his part of the job.
I don't know why I answer to this post, because actually, the biggest mistake was in the slashdot article: "The best person to assure quality is the developer"... This is oh soooo false.
phobos% cat
oops... sorry... my first language is not English, but i still can see many stupid mistakes in the message i have just submitted.
.sig
phobos% cat
I read some parts of it. Actually, i read one part, then click on a link to the same page, read another part, and there are contradictions. I don't mean that the author is not serious, but he doesn't seem that much objective. Example: he says that all decoders do the same things, but winamp got artefacts, and right under, there is an update saying that only winamp and 2 other players render perfectly mp3 files.
.sig
Anyways, i do honestly believe that there is a difference (you asked me), but I can be wrong. My computer is not plugged in my best amp (which i use more often), i do listen sometimes to cds on my computer (using the same amp) and for some types of music (crisp ambiant music - eg aphex twin - and classical music) it just doesn't feel the same.
As I said, i don't believe a hard drive is portable (in the same sense as a cassette player and a new discman are).
phobos% cat
A MP3 device with 80Gb+ that is used for rips of cds you own with the output redirected to your stereo system is only more useful than a Pioneer 100-disk changer... if you are deaf.
.wav player...
.sig
I mean, who would want to downgrade the quality of the cds he paid for. Maybe if it was a
I have nothing against this player (is it really that portable? how much can i carry my 20gig WD ide drive in my backpack without breaking it?) but mp3 is not lossless compression.
Please.
phobos% cat
From the linked page:
;)
.sig
SCOOP: Sources discussed the ins and outs of Apple's first publicly available, modern OS.
Mmmm... can't wait to read those sources...
phobos% cat
I am not an expert on the subject, but i have always felt that the potential for overclocking was what the margin between the maximum working speed of the chip - this is known by the company (Intel, Amd, etc.) - and the speed at which the chip is running "comfortably".
.sig
I have always wondered if a company A could make a chip with the same performance as company B, but send it out on the market at 100mhz faster than it's rival. (which would then be compared in price with company B's faster chip)
I mean, if the "safety margin" is subjective and there are no standards, how can i compare company A and B's chips?
And when AMD removes it's multiplier, how can i know if it is because:
1) they are loosing money on overclockers - really?
2) they are pushing a bit too much on their new chips and don't wan't people to notice their "safety margin" is smaller?
Actually, I don't know that much in hardware, so I could be totally wrong. Correct me if necessary...
phobos% cat
Erm... actually, viewing it at 24-bit color does the same thing... that's the point of this really-web-safe pallette, isn't it?
phobos% cat
No, i don't want to bookmark every site i visit.
No, i won't go to the site if i can't type it's address.
- What if they decide to host an english section?
- These addresses would be limited to small communities sites and would not help the fact that you have the opportunity to reach a gobal public as you said.
Actually, modern desktop computers all share a common character set: ASCII. Let's use it. Actually, this address is only an easier thing to remember than a numerical IP (XXX.XXX.XXX.XXX)...phobos% cat
Information from Other Sources
For reasons such as improving personalization of our service (for example, providing better product recommendations or special offers that we think will interest you), we might receive information about you from other sources and add it to our account information. We also sometimes receive updated delivery and address information from our shippers or other sources so that we can correct our records and deliver your next purchase or communication more easily.
{...}
What Choices Do I Have?
{...}
Click here to explore products that offer anonymous browsing. In addition, the Federal Trade Commission provides useful information about online privacy on its own Web site, Site Seeing on the Internet.
Dear customer,
We are building a large distributed database of your personal information. This information can get out of our hands at any time so, to ensure that other companies get the right information, we will even update it automagically by sharing info between our "circle-of-friend-companies-we-trust-and-you-can-a lso-trust-cause-they-are-pretty-and-love -flowers-and-all" and using high-tech heuristics to be sure we know precisly where you live and if you wear boxers of briefs.
What Choices Do I Have?
Oh well... grrr...Actually, you need a big and complex piece of software whose only goal is to guard you from big companies like us. We sure hope it's got better heuristics than ours. Actually, it's a big game! You try to hide your info, and we try to get it! If we win, you don't know, but if you do win, you may get a prize!
Dear sir ~MegamanX~, this is Joe from Amazone. You won a car in the privacy contest. Could you give us your address so we can ship it to you. Check here if you want to receive emails of our special offers...
phobos% cat
Everybody knows it's much better to:
- Never redesign anything. Never evoluate.
- Always keep backward compatibility since a standard is really usefull when there are 10 ways to do the same thing. It is so much cleaner.
We should all realize Java is heading the wrong way...(yeah right)
phobos% cat
Actually, there are many girls studying math. More than guys, iirc...
.sig
phobos% cat
From the article:
.sig
The count parameter is always set to the value 1 by the calling code. The byte read from the file descriptor fd into the RandBuf buffer is subsequently overwritten with the read() function's return value, which will be 1. The actual random data are not used.
Err... did i miss something?
phobos% cat
If you have a legitimate reason to look at youngass.jpg, then surely you don't care if you are singled out and perhaps emailed by the server admin asking why you are requesting that file.
.sig
Come on... this is suuuch a false statement.
I am NOT a racist, but i WOULD care if someone wrote on a big wall that i was one... come on...
Even if you and your wife/children/parents know that you aren't a pedophile, would you like it if someone "proved" it and people started acting funny around you, talked in your back, etc??? Even if there is only a tiny possiblilty that people around you hear about it? No, you wouldn't like it. Even if you know that probably nobody you know will trace you, there is a doubt.
Face it.
phobos% cat
I'm sorry to say that, but I think you should get a life.
.sig
Makes me laugh how some people here think they are The Omniscient Wise Guy That Rules The Internet.
Thus France suffers from high unemployment and a lack of capital for new business start ups. When is the last time you bought anything that said "Made in France."
Yes, I just bought an Airbus and plenty of other examples yesterday, but you wouldn't believe me.
Everybody in france is poor, sad and sick. It probably is because they don't do as you expect them to do, as they should do (== as the US do). They will never do anything good in software developpement and in any science. I think they are on the road to become bankrupt by the end of next year. (feel the irony)
Look at the subject of your post, damnit! Doesn't it sound stupid and "prétentieux" to you?????? You just made my day...
(Sorry for my english, my first language is french (i'm from Québec)...)
phobos% cat
hahaha ;) nice one.
.sig
But as you can see, it still is not enough for them... They have better eyes than me. 'cause i never saw the difference between 89fps and 113fps... but i can see one between 640x480 and 1600x1200... anyways... next time 3dfx will know what to do. Just remove visual features and give them 600fps 640x480... Maybe they also should slack on their Linux support too.
(the usual flaimbait here, i have to do it:
seems that it doesn't work quite right with Athlons... and i just read an article about incompatibilities between Athlons and GeForces... and Athlons and memory, motherboards, etc...
If I overclocked my coppermine and my voodoo, i swear i would do better in stability, compatibility and speed than you all with your "factory overclocked" Athlons+nVidea...;)
phobos% cat
How dare you say anything against Talk City?! Their polls are so interesting!
.sig
Topic: What is the best area of the country to raise a family?
o West coast
o Midwest
o South
o East coast
| Vote now! |
8-P
phobos% cat
What a coincidence! wow!
.sig
This morning i wanted to know how cool and big your University was! Man, i'm impressed, you answered me the same day!
There must be a god!
phobos% cat
If we could "Print Screen", it would mean that the data is not encrypted in video memory. Since we got computers(!), i believe it would be a bit simpler to read the video memory (emulate a keypress on "print screen" if you wish) between every frame. And this would be no problem.
.sig
But if they are smart, data will be encrypted all the time up to when it reaches the chip in the monitor.
phobos% cat
All the Windoze people have to say is, "Great. Now let's try the same thing on six new identical machines with redundant power supplies and drive arrays, just like you would do with a critical server in the real world."
;)
.sig and english is not my first language, but i'm still a good guy;) .sig
I don't know, but would we be testing the redundancy mechanism more than the OS in that case? I understand that 2 computers are a relatively small sample (!), but as long as both computers had about the same hardware, you'll have to admit that NT was really not lucky
As for the redundancy, wouldn't it hide most of the OS problems? I mean... Micosoft's www site did not go down for some time, does that mean that windoze NT is really reliable or that a ~= 350 servers farm is enough to hide faulty servers?
Maybe with a more reliable OS companies would need less redundancy...
(I have no
phobos% cat
The CS department also made the move from IRIX to Linux (!) when they bought a big number of new Intel based stations. And here, everything has always been done on *nix systems. The support is not incredible here either... but it's understandable, i think. CS students should be able to install and configure a Linux distro by themselves (i mean get the info without the help of a support team... they should be able to use the Internet, shouldn't they? shouldn't they??;) Another way to work is also to work at school... or from a telnet terminal in a win32 environnement (!). There are no reasons why universities shouldn't use a free and stable operating system like Linux. -MegamanX .sig
phobos% cat