But the example the reporter gave was of key based encryption being brute forced. Shouldn't that, by his definition, be a bounded problem? There are only so many x bit numbers. If you use 128 bit encryption, then you have =2^128 possible keys to try.
128-bit brute-force anything is a bounded problem. Since there are only 2^128 possible inputs, all you have to do is pick the longest time it takes your program to run out of all those 2^128, and you can say your program runs in constant time (or better).
I have time to kill, am very interested in theoretical CS, and am a karma whore. Therefore I will now explain P vs NP in detail, in case anyone wants an explanation. I used
this article to verify some of the fine points.
P and NP are classes of decision problems: problems in which you are presented with an input and must say "yes" or "no". For example, "Is this a prime number?" and "Is there a path from A to B on this graph (network)?" are decision problems.
A problem is in P if you can write a computer program to solve it in "polynomial" time. What that means is this: you give me a program, a polynomial (like 3*n^3) and a starting number m. Whenever your program is given an input, it must say "yes" or "no" within 3*n^3 time units. If the program you gave always gives the right answer in 3*n^3 steps (or whatever the polynomial was) for *any* input that's n symbols long, where n>=m, then the problem is in P. If no program and polynomial exist that satisfy this, then the problem is not in P. It's hard to prove that a problem is not in P, because you have to prove that no program at all can solve it.
NP is a bit more complicated. The definition is essentially the same as for P, except the program runs on a very strange kind of computer. One way of thinking of it is that it has a magic coin. Any time the program wants, it can flip the magic coin and decide what to do according to the whether the coin shows heads or tails. For example, if the computer wants to check if a number is composite (not prime), it can flip the coin a whole bunch of times to get the digits of a possible factor of the program. Here's the really confusing part: when you run the program, the computer actually tries every possible sequence of coin flips. If there is at least one sequence of flips that would get the program to say "yes", then the computer says "yes". If every single sequence says "no", then the computer says "no". So if the program wants to check if a number is composite, all it needs to do is flip the coin a few times to get a possible factor, and say whether that factor divides the number. If the number is composite, then at least one sequence of flips will generate a factor and the program will say "yes". NP stands for "non-deterministic", which is a good description of the weird computer.
A problem is in NP if the weird computer can solve it in polynomial time. Note that every problem in P is also in NP: if a normal computer can solve it without a magic coin, then so can the NP computer.
The question P=NP is the following: can every problem that can be solved in polynomial time on the weird computer also be solved in polynomial time (possibly with a larger polynomial) on a normal computer?
Two more definitions:
A problem is NP-hard if every problem in NP is reducable to it. For example, the
satisfiability problem is NP-hard. If you give me a problem that can be solved in NP, I can make a very simple and quick program that will take any input to your problem and turn it into an equivalent input for the satisfiability problem.
A problem is NP-complete if it is NP-hard and also in NP. Satisfiability is NP-complete because it's NP-hard but can be solved in NP. A program that is NP-hard but not in NP is more difficult to solve than problems in NP.
I hope I didn't just confuse you more... just read the wikipedia article if this doesn't help.
It's an hourly log of the number of minutes I waste on slashdot...
01010 = 10
01000 = 8
01101 = 13
00100 = 4 ...
Seriously, though, what is the general name for a string of symbols if it isn't data? Is "random data" an oxymoron?
Reading a few other threads close to this one, the answer seems to be an undistinct "yes! no! yes! no!...", so I guess it's a matter of opinion.
I sometimes use the word in ways similar to "copy the data from my hard disk" or "generate pseudorandom data" or "data transfer rate of 10Gbps". Unless I am relatively unique in this usage, I conclude that for many people, "any string of symbols" or at least "any string of symbols readable by a computer or human" is at least one possible definition for data.
Reading dictionary entries, I see a lot of references to phrases like "factual information" or "basis for reasoning" in dictionary entries on the subject, so maybe my interpretation is wrong as far as most dictionaries are concerned. But what are dictionaries for, except to reflect the common language, including new words like the vorb "google"?
As I said, opinions seem to be divided on the subject, so I guess I'll just leave it at that. I'd be interested to hear replacements for the word data in the phrases I mentioned above, or arguments that what I'm referring to actually has meaning or "structure".
...it's not as if you'd have a way to detect when you'd achieved it even if it was achievable.
What about correctness proofs?
If "100% secure" has any meaning at all, I'd say it means the software does what it's expected to. Although it's probably not practical at the moment, it's not impossible to write a provably correct OS and software.
Of course, that doesn't prove that the CPU and other hardware running the software doesn't have flaws that make the computer insecure, but that doesn't mean the OS itself can't be called completely secure. It's like running a completely provably secure web browser on a mere mortal operating system: the browser can still be called secure even if it isn't in that context.
I suppose one could also say that the specifications themselves could have bugs in them, especially since they might have similar complexity to the software... but it's still something to think about.
Anyway, in general, I agree with you. Although a quick google search for "provably correct operating system" returned at least one interesting
result, I doubt if anything as powerful as Linux or Windows will be made this way in a long long time.
I just don't like it when people assume that computer science cannot be anything other than empirical.
Sorry, I was just trying to pick a super-slow language at random... but now that I think about it, I guess any reasonably popular language will have a fast compiler or an almost-as-fast byte code.
Don't get me wrong, I'm no C phanatic. Haskell is my language of choice, compatability permitting. The purpose of my post was to defend C, not to attack other languages.
Speed. How many programming-language benchmarks are there that don't find C to produce the fastest code, not counting assembly/machine code? For example, interpreted languagues like LISP are completely impractical for something like a raytracer, unless someone makes a miraculously good LISP compiler.
Also, C is something of a standard language. At least on UNIX-style systems, programs written in any other language have to use some glue-code library to allow them to use standard libraries, system calls, etc. (C++ is close enough to C not to, but I've had a few frustrations with C++ symbols being named differently from C symbols.)
Anyway, any language that allows you to do everything that C does also allows you to make the same mistakes. Yes, it's probably easier to make them in C than, say... *ducks* Pascal, but it's not an insurmountable problem.
To be honest, I've never written a C program that required any security, but I hope this helps anyway.
OpenBSD is a particular flavour of BSD that is famous for its security. Mac OS X does indeed run on top of a a flavour of BSD, but the post was referring to OpenBSD in particular, which is probably the most secure flavour of BSD there is.
(No, Windows doesn't get brownie points for using BSD's TCP/IP stack.)
Slashdot Mirror
No, see, it encoureages you to get slashdot off your screen and work. That's what makes it a productive colour.
I have time to kill, am very interested in theoretical CS, and am a karma whore. Therefore I will now explain P vs NP in detail, in case anyone wants an explanation. I used this article to verify some of the fine points.
P and NP are classes of decision problems: problems in which you are presented with an input and must say "yes" or "no". For example, "Is this a prime number?" and "Is there a path from A to B on this graph (network)?" are decision problems.
A problem is in P if you can write a computer program to solve it in "polynomial" time. What that means is this: you give me a program, a polynomial (like 3*n^3) and a starting number m. Whenever your program is given an input, it must say "yes" or "no" within 3*n^3 time units. If the program you gave always gives the right answer in 3*n^3 steps (or whatever the polynomial was) for *any* input that's n symbols long, where n>=m, then the problem is in P. If no program and polynomial exist that satisfy this, then the problem is not in P. It's hard to prove that a problem is not in P, because you have to prove that no program at all can solve it.
NP is a bit more complicated. The definition is essentially the same as for P, except the program runs on a very strange kind of computer. One way of thinking of it is that it has a magic coin. Any time the program wants, it can flip the magic coin and decide what to do according to the whether the coin shows heads or tails. For example, if the computer wants to check if a number is composite (not prime), it can flip the coin a whole bunch of times to get the digits of a possible factor of the program. Here's the really confusing part: when you run the program, the computer actually tries every possible sequence of coin flips. If there is at least one sequence of flips that would get the program to say "yes", then the computer says "yes". If every single sequence says "no", then the computer says "no". So if the program wants to check if a number is composite, all it needs to do is flip the coin a few times to get a possible factor, and say whether that factor divides the number. If the number is composite, then at least one sequence of flips will generate a factor and the program will say "yes". NP stands for "non-deterministic", which is a good description of the weird computer.
A problem is in NP if the weird computer can solve it in polynomial time. Note that every problem in P is also in NP: if a normal computer can solve it without a magic coin, then so can the NP computer.
The question P=NP is the following: can every problem that can be solved in polynomial time on the weird computer also be solved in polynomial time (possibly with a larger polynomial) on a normal computer?
Two more definitions:
I hope I didn't just confuse you more... just read the wikipedia article if this doesn't help.
It's an hourly log of the number of minutes I waste on slashdot...
...
01010 = 10
01000 = 8
01101 = 13
00100 = 4
Seriously, though, what is the general name for a string of symbols if it isn't data? Is "random data" an oxymoron?
Reading a few other threads close to this one, the answer seems to be an undistinct "yes! no! yes! no!...", so I guess it's a matter of opinion.
I sometimes use the word in ways similar to "copy the data from my hard disk" or "generate pseudorandom data" or "data transfer rate of 10Gbps". Unless I am relatively unique in this usage, I conclude that for many people, "any string of symbols" or at least "any string of symbols readable by a computer or human" is at least one possible definition for data.
Reading dictionary entries, I see a lot of references to phrases like "factual information" or "basis for reasoning" in dictionary entries on the subject, so maybe my interpretation is wrong as far as most dictionaries are concerned. But what are dictionaries for, except to reflect the common language, including new words like the vorb "google"?
As I said, opinions seem to be divided on the subject, so I guess I'll just leave it at that. I'd be interested to hear replacements for the word data in the phrases I mentioned above, or arguments that what I'm referring to actually has meaning or "structure".
If "100% secure" has any meaning at all, I'd say it means the software does what it's expected to. Although it's probably not practical at the moment, it's not impossible to write a provably correct OS and software.
Of course, that doesn't prove that the CPU and other hardware running the software doesn't have flaws that make the computer insecure, but that doesn't mean the OS itself can't be called completely secure. It's like running a completely provably secure web browser on a mere mortal operating system: the browser can still be called secure even if it isn't in that context.
I suppose one could also say that the specifications themselves could have bugs in them, especially since they might have similar complexity to the software... but it's still something to think about.
Anyway, in general, I agree with you. Although a quick google search for "provably correct operating system" returned at least one interesting result, I doubt if anything as powerful as Linux or Windows will be made this way in a long long time.
I just don't like it when people assume that computer science cannot be anything other than empirical.
Sorry, I was just trying to pick a super-slow language at random... but now that I think about it, I guess any reasonably popular language will have a fast compiler or an almost-as-fast byte code. Don't get me wrong, I'm no C phanatic. Haskell is my language of choice, compatability permitting. The purpose of my post was to defend C, not to attack other languages.
Speed. How many programming-language benchmarks are there that don't find C to produce the fastest code, not counting assembly/machine code? For example, interpreted languagues like LISP are completely impractical for something like a raytracer, unless someone makes a miraculously good LISP compiler.
Also, C is something of a standard language. At least on UNIX-style systems, programs written in any other language have to use some glue-code library to allow them to use standard libraries, system calls, etc. (C++ is close enough to C not to, but I've had a few frustrations with C++ symbols being named differently from C symbols.)
Anyway, any language that allows you to do everything that C does also allows you to make the same mistakes. Yes, it's probably easier to make them in C than, say... *ducks* Pascal, but it's not an insurmountable problem.
To be honest, I've never written a C program that required any security, but I hope this helps anyway.
OpenBSD is a particular flavour of BSD that is famous for its security. Mac OS X does indeed run on top of a a flavour of BSD, but the post was referring to OpenBSD in particular, which is probably the most secure flavour of BSD there is.
(No, Windows doesn't get brownie points for using BSD's TCP/IP stack.)