Re: Imaginary Polynomial Time Algorithm for Subset sum Problem

On Thu, 06 Mar 2008 21:47:54 +0100, Tim Tyler <seemysig@xxxxxxxxxxxxxx> wrote:

Jym wrote:
Tim Tyler <seemysig@xxxxxxxxxxxxxx> wrote:
Jym wrote:

In case of parallel register machine, for example, you have a "fork" operation that create a new process and each process execute in parallel no matter how many of them there is. Obviously, this is unrealistic and allow to create 2^n process (hence, 2^n "computer power") in time n and then use them to solve whatever you want.

A huge parallel computer is OK with me - it is the same type of idea
as a Turing machine having an infinite tape.

Big, parallel computers still have processing limitations - in that
there are limits to the speed information can be propagated about
and there are still processes with temporal dependencies.
PRM, for example, don't have this limitation.
They can't send info from one processor to the other, except when creating one or when computation is done (and the info goes back to the "father"). But creating/dying always takes a single unit of time, no matter how many processors are already active. [...]

In practice, "fork" operations are limited by "fan in" effects - too many of them in a short space of time, and there's nowhere nearby to
represent the new processes.

If your hypothetical machine can always execute fork operations
in constant time, then it can't be physically constructed.

Absolutely.
And that's also the reason why it can solve Pspace problems in polynomial time without jeopardizing empiric results (and Cook's thesis) that the (realistic) computational model doesn't matter for characterising complexity classes.
Yet, it is useful for theoretical purpose.

And that's also the problem with the OP stamping process: it can copy an arbitrarily large number of dots in a single unit of time. While on any realistic computer/model, copying an array (typically), would take time proportional to its size.
If you consider that the stamping process takes time proportional of the number of dots to copy, then the OP's algorithm require exponential time to solve the subset sum problem. No big news.

--
Hypocoristiquement,
Jym.
.

Relevant Pages

  • Re: A type 2 error has occurred .. +bbq
    ... But you overestimate my girlfriend's familiarity with computers; ... No matter (but more difficult in a relationship .. ... Well, I'm an engineer, and I love good food. ... I did 'catering' at college and don't like 'bad food' of course. ...
    (uk.comp.sys.mac)
  • Re: Windows Common LISP
    ... This may be a matter of religion, ... practical considerations or the toss of a coin: ... many computer vendors simply pre-install Windows on everything ... that computers can be bought naked or, sometimes, with other OSes ...
    (comp.lang.lisp)
  • Re: Other fixed points for h(e^pi/2) = +-i
    ... why that, why we choose certain cuts etc), no computers ... No matter what these fixed points are, ... If you wish, email me at jgal ath dot forthnet dot gr, and I will send you ... Otherwise you will end up going round and round in circles. ...
    (sci.math)
  • Re: Hdd Detection With XP.
    ... | Thank you all kindly for your attention to this little matter .I did not ... | drive and reboots this erratic behavior will continue untill I shut the ... | puzzled,which is a rare event where simple computers are concerned,so,, ... | Again Thank You all,for your time and attention. ...
    (microsoft.public.windowsxp.basics)
  • Re: Imaginary Polynomial Time Algorithm for Subset sum Problem
    ... operation that create a new process and each process execute in parallel no matter how many of them there is. ... as a Turing machine having an infinite tape. ... parallel computers still have processing limitations - in that ... But creating/dying always takes a single unit of time, no matter how many processors are already active. ...
    (comp.theory)