Re:There are no NP problems, only NP solutions.
on
Does P = NP?
·
· Score: 3
There is no recursive solution to the halting problem. It may be that there is a physically possible, non-recursive solution, which would invalidate Church's Thesis, but no mathematics.
You show that a problem is NP complete by showing how a PTIME solution of this problem can be transformed into a PTIME solution of all NP hard problems. It can only be misclassified if there is a mistake in this proof.
The boring source of these problems is version numbering schemes that suggest that builds are actual successors to earlier releases. The Mozilla milestone approach, and the linux-kernel `test' and `pre' releases can help to avoid this.
Still, it is exceptionally incompetent of Redhat to release a distribution based on code generated using an unfinshed compiler whose binaries are incompatible with existing official releases.
Everyone knows? I think IBM's interest in Linux is sincere. IBM have been the UNIX vendor whose participation in the UNIX standardisation process was most genuine and least Machiavellian, and I think they see Linux doing what AIX failed to: provide a kind of default standard for UNIX. It would be great if some of their administration tools were to migrate over to Linux...
SLOW could be simulated in software on the ZX80. It took about 400 bytes of code (half the default size of the RAM:->) but it worked well enough. There was even a commercial game released that used it...
Which was the first computer depends upon your criteria for what is a computer. If I have it right, the American machines were very easy to reconfigure machines, that performed computations from an electronic memory, but their instruction set was not Turing complete. The Zuse machine had a Turing complete instruction set, and so would get my vote for first computer, but it wasn't until the Bletchley machine that code and data resided in the same memory space, which is of course a very important aspect of modern computer design.
Choose your criteria to get your favourite machine to win...
I think it is a bit premature to talk of W2k's demise...
Other than that I thought the article made a reasonable point. Sun hardware is really a long way ahead of Intel-based for SMP, and SMP is still much easier to write software for than clusters. The importance of Linux for the traditional UNIX user is that it seems to be setting the pace for UNIX interoperability.
The constitution of the vote has been deliberately withheld, so for all we know the vote was 5-4. The figure of an 8-1 decision comes from the fact that there was only one published dissenting view (Justice Breyer), but there may have been other unpublished dissenting views.
From the Kernel Traffic summary, it seems that Jeff Merkey had told MS about his work on NTFS, and MS had explicitly OKed this work. If this is so, then they cannot use this intellectual property argument.
The optimisation done by the Crusoe is much more ambitious than that done by released Intel processors. Rememebr that the Crusoe is a VLIW processor which is capable of executing four microcode instructions at a time. I guess the new VLIW Intels will do the same, but for now the Crusoe technology is much more advanced than the Intel stuff.
I agree about performance, but the engineering really does live up to the promised `very cool'. I think the performance delivered in January was a disappointment: I think they had been hoping to beat Intel chips of a comparable clock rate.
Quite so. Several user surveys have shown that long battery life and low size/weight are the two most important qualities for most people.
Still the Crusoe won't make that much of a difference until the power usage of other components starts to come down. I recall that the Crusoe has some support for reducing usage of other online components by building a model of their operation ob board. If successors of the Crusoe can actually simulate other circuitry and so reduce the chipset count, that would be another big win both for power consumption and performance.
I'm familiar with the law only indirectly: the same principles were invoked with the mandate of tracking devices for mobile phones. In that case the federal legislation imposes technical capabilities the mobile phone operators must meet, but how they meet the criteria is up to them. That I understood is a direct analogue of the wiretap legislation.
I think the Cringely suggestion is a bit tongue-in-cheek, but it seems perfectly plausible that there is some switching or spoofing capability built into these boxes. If so, the capabilities should be discussed openly. If not, as Cringely put it, why the box?
The analogy doesn't work. Wiretaps are carried out by telephone companies using their own technology: they have to make it possible to do so, but they domn't have to smuggle in any mysterious black box.
The fuss about Carnivore is it breaks with this model, and with no convincing explanation. You don't need to be paranoid to suspect there is more to this device than the FBI alleges. (Cringely suggested it might contain a sabotage device...)
I think the right conclusion is very close to this: UNIX is very good at solving a lot of low-level technical issues, and the best cross-architecture platforms out there are UNIXes. But they have awful, unforgiving user interfaces. It's roughly the conclusion I take from the Unix-hater's handbook, etc.
I know this article, and the point it makes is not convincing. It doesn't disagree with the main points: that the Intel is a CISC instruction set transformer bolted onto an underlying RISC architecture, and that hardware emulation is faster than software emulation.
It does make the point that it would be better if we all used RISC. So what? The failure of RISC is that it hasn't convinced the world that it is worth making the transition.
The real danger to Intel is that it is has been falling behind Moore's law for five years now, and the way out, sooner or later, will be SMP, which is hard to do well for x86 architecture.
It isn't absurd, but it is based on a broken model of information. The point is that if you give me a copy of your song in whatever format, either it is in principle possible for me to play it, in which case I can copy it, or it is not. Self-destructive media is not the same as self-destructive information.
The media companies don't want to change the way they work to fit this fact, so they are trying all kinds of strageties to get around it. All of them have problems:
Stitching up the market: authorised players, etc. Relies on the fact (vain hope) that no-one breaks ranks.
Legal tactics: it's illegal to contravert an encryption method. This screws up fair use.
Tracking use of media: signing copies etc.. This is an invaison of privacy.
If the companies can either adjust their economic model, or come up with a model of restrictions which doesn't have obnoxious side-effects, then good for them. But until then, they deserve their bad press.
Not necessarly a huge problem: you can simply copy code from ROM to RAM when you boot the machine. Or more economically, you can have a minimal OS on the machine that downloads and unpacks the regular installation from the network.
...or whose company didn't press for speedy resolution of the cases (most green card applications are fought for by company lawyers, whose interests don't necessarily coincide with that of the immigrant), or who come from a country with a lot of competeing applicants, and find their case being pushed back and back by quota restrictions.
There is nothing determinate about the length of these processes. They needn't terminate within six years.
Slashdot Mirror
There is no recursive solution to the halting problem. It
may be that there is a physically possible, non-recursive solution,
which would invalidate Church's Thesis, but no mathematics.
You show that a problem is NP complete by showing how a PTIME solution
of this problem can be transformed into a PTIME solution of all NP
hard problems. It can only be misclassified if there is a mistake in
this proof.
gcc 2.96 generates binary incompatible C code.
suggest that builds are actual successors to earlier releases. The
Mozilla milestone approach, and the linux-kernel `test' and `pre'
releases can help to avoid this.
Still, it is exceptionally incompetent of Redhat to release a
distribution based on code generated using an unfinshed compiler whose
binaries are incompatible with existing official releases.
Everyone knows? I think IBM's interest in Linux is sincere. IBM have
been the UNIX vendor whose participation in the UNIX standardisation
process was most genuine and least Machiavellian, and I think they see
Linux doing what AIX failed to: provide a kind of default standard for
UNIX. It would be great if some of their administration tools were to
migrate over to Linux...
SLOW could be simulated in software on the ZX80. It took about 400 :->) but it worked
bytes of code (half the default size of the RAM
well enough. There was even a commercial game released that used
it...
computer. If I have it right, the American machines were very easy to
reconfigure machines, that performed computations from an electronic
memory, but their instruction set was not Turing complete. The Zuse
machine had a Turing complete instruction set, and so would get my
vote for first computer, but it wasn't until the Bletchley machine
that code and data resided in the same memory space, which is of
course a very important aspect of modern computer design.
Choose your criteria to get your favourite machine to win...
No, the x86 is recognised to be a bad architecture to do SMP with.
Solaris only shines on Sun hardware. It's pretty ropey on Intel hardware; it's only there to make it possible to run Sun only shops.
Other than that I thought the article made a reasonable point. Sun
hardware is really a long way ahead of Intel-based for SMP, and SMP is
still much easier to write software for than clusters. The importance
of Linux for the traditional UNIX user is that it seems to be setting
the pace for UNIX interoperability.
The constitution of the vote has been deliberately withheld, so for
all we know the vote was 5-4. The figure of an 8-1 decision comes
from the fact that there was only one published dissenting view
(Justice Breyer), but there may have been other unpublished dissenting
views.
I think there is reason to doubt Merkey's account of things, but if what he says is true, then MS have no case.
From the Kernel Traffic summary, it seems that Jeff Merkey had told MS
about his work on NTFS, and MS had explicitly OKed this work. If this
is so, then they cannot use this intellectual property argument.
done by released Intel processors. Rememebr that the Crusoe is a VLIW
processor which is capable of executing four microcode instructions at a
time. I guess the new VLIW Intels will do the same, but for now the
Crusoe technology is much more advanced than the Intel stuff.
I agree about performance, but the engineering really does live up
to the promised `very cool'. I think the performance delivered in
January was a disappointment: I think they had been hoping to beat
Intel chips of a comparable clock rate.
low size/weight are the two most important qualities for most people.
Still the Crusoe won't make that much of a difference until the
power usage of other components starts to come down. I recall that
the Crusoe has some support for reducing usage of other online
components by building a model of their operation ob board. If
successors of the Crusoe can actually simulate other circuitry and so
reduce the chipset count, that would be another big win both for power
consumption and performance.
Freenet is of course an approach to peer to peer file sharing that tries to address these scalability issues. Shame the article doesn't mention it.
Indeed. I remember the little circuit project books they used to distribute ofr next to nothing. Nothing else was like it.
invoked with the mandate of tracking devices for mobile phones. In
that case the federal legislation imposes technical capabilities the
mobile phone operators must meet, but how they meet the criteria is
up to them. That I understood is a direct analogue of the wiretap
legislation.
I think the Cringely suggestion is a bit tongue-in-cheek, but it
seems perfectly plausible that there is some switching or spoofing
capability built into these boxes. If so, the capabilities should be
discussed openly. If not, as Cringely put it, why the box?
companies using their own technology: they have to make it possible to
do so, but they domn't have to smuggle in any mysterious black box.
The fuss about Carnivore is it breaks with this model, and with no
convincing explanation. You don't need to be paranoid to suspect
there is more to this device than the FBI alleges. (Cringely
suggested it might contain a sabotage device...)
I think the right conclusion is very close to this: UNIX is very good
at solving a lot of low-level technical issues, and the best
cross-architecture platforms out there are UNIXes. But they have
awful, unforgiving user interfaces. It's roughly the conclusion I
take from the Unix-hater's handbook, etc.
doesn't disagree with the main points: that the Intel is a CISC
instruction set transformer bolted onto an underlying RISC
architecture, and that hardware emulation is faster than software
emulation.
It does make the point that it would be better if we all used RISC.
So what? The failure of RISC is that it hasn't convinced the world
that it is worth making the transition.
The real danger to Intel is that it is has been falling behind
Moore's law for five years now, and the way out, sooner or later, will
be SMP, which is hard to do well for x86 architecture.
point is that if you give me a copy of your song in whatever format,
either it is in principle possible for me to play it, in which case I
can copy it, or it is not. Self-destructive media is not the same as
self-destructive information.
The media companies don't want to change the way they work to fit
this fact, so they are trying all kinds of strageties to get around
it. All of them have problems:
fact (vain hope) that no-one breaks ranks.
This screws up fair use.
of privacy.
If the companies can either adjust their economic model, or come up
with a model of restrictions which doesn't have obnoxious
side-effects, then good for them. But until then, they deserve their
bad press.
Not necessarly a huge problem: you can simply copy code from ROM to RAM when you boot the machine. Or more economically, you can have a minimal OS on the machine that downloads and unpacks the regular installation from the network.
Check out the Diskless nodes Linux HOWTO. It describes the hows and whys of exactly this.
(most green card applications are fought for by company lawyers, whose
interests don't necessarily coincide with that of the immigrant), or
who come from a country with a lot of competeing applicants, and find
their case being pushed back and back by quota restrictions.
There is nothing determinate about the length of these processes.
They needn't terminate within six years.