Starting a seperate news group "comp.quantum-computers"
era...@gmail.com
Is it time yet to start a seperate newsgroup on USENET "comp.quantum-
computers"
Nature seems to have built quantum in us --- check my previous posting
on how a quantum neural network seems to explain human sacchadic eye
movements ----
and check my posting on comp.ai.philosophy asking whether a 2-
dimensional planar transistor which answers "00", "01", "10", "11"
simultaneously can be used to build a quantum neural network -------
so far it seems the other quantum computers built are unstable.
Best Regards,
Erach
ps. Please send me votes YES or NO which I can submit to the USENET
authorities to start a comp.quantum-computers newsgroup
-------------------------- and if you have done this before,
how to start this newsgroup.
John Ladasky
> Hi all,
> Is it time yet to start a seperate newsgroup on USENET "comp.quantum-
[snip]
> ps. Please send me votes YES or NO which I can submit to the USENET
> authorities to start a comp.quantum-computers newsgroup
Erach,
I submit to you, simultaneously, one "yes" vote and one "no"
vote. :^P
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Ladasky Home Solar, Inc.: blowing sunshine up your |
| power grid since March 24, 2005. Fiat lux! |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| Uptime Downtime kWh generated kWh consumed |
| 765.5 days 13 hours 13341 14738 |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
era...@gmail.com
has demonstrated a quantum computer (and for sceptics, there are
several technical articles in little-known journals, so says the web)
and is planning to give free accounts to program a quantum computer.
D-Wave's web-site is http://www.dwavesys.com
This should be great for PhD hunters.
Erach
Contact
D-Wave Systems Inc.
100 - 4401 Still Creek Drive
Burnaby, British Columbia
Canada
V5C 6G9
Telephone: (604) 630-1428
Fax: (604) 630-1434
For business inquiries: bus...@dwavesys.com
For media inquiries: me...@dwavesys.com
For investor inquiries: inve...@dwavesys.com
For scientific and technical inquiries: tech...@dwavesys.com
For all general inquiries: in...@dwavesys.com
Ben Rudiak-Gould
> D-Wave Inc. (I read in the various news articles on the net)
> has demonstrated a quantum computer (and for sceptics, there are
> several technical articles in little-known journals, so says the web)
> and is planning to give free accounts to program a quantum computer.
I met an employee of D-Wave a few months ago and I believe they're legit,
but I don't think there's much practical value in this offer; you'd almost
certainly get much better turnaround times from an emulator running on your
local machine. The only advantage of using the real hardware is that you
might find bugs in it (or in quantum mechanics, but I doubt that).
-- Ben
Traveler
wrote:
>D-Wave Inc. (I read in the various news articles on the net)
>has demonstrated a quantum computer (and for sceptics, there are
>several technical articles in little-known journals, so says the web)
>and is planning to give free accounts to program a quantum computer.
>
>D-Wave's web-site is http://www.dwavesys.com
>
>This should be great for PhD hunters.
>
>Erach
>
>Contact
>
>D-Wave Systems Inc.
>100 - 4401 Still Creek Drive
>Burnaby, British Columbia
>Canada
>V5C 6G9
>
>Telephone: (604) 630-1428
>Fax: (604) 630-1434
Everyone working on quantum computers is either a fraud or a fool or
both. That includes the folk at D-Wave. Quantum physicists do not
understand why the universe is probabilistic. David Deutsch has his
infinite parallel universes crap he's been preaching for aeons while
most others admit that they have no clue. Deutsch is a full blown
crackpot of the worse kind in my book. His crap is no better than the
time travel, paranormal crap of that other crackpot, Jack Safarti.
Come to think of it, Deutsch believes in the possibility of time
travel as well. How any of these lunatics get to be taken seriously by
the mainstream physics community is a mystery.
The truth is that the universe is probabilistic because it is discrete
and there is only one fundamental discrete interval (i.e., a universal
event counter). Since nature cannot calculate precise intervals for
interactions, it is forced to use the only alternative: probability.
In other words, all interactions have the same fundamental duration
but the timing of interactions is probabilistic. BTW, this is the
reason for the probabilistic decay of subatomic particles. What's
important is that, in the end, all conservation laws are obeyed.
Telling it like I see it.
Louis Savain
Why Software Is Bad and What We Can Do to Fix It:
http://www.rebelscience.org/Cosas/Reliability.htm
era...@gmail.com
Actually programming a quantum computer should be quite simple ----
just map your problem's NP complete portion to the D-wave quantum
computer's NP complete problem --- and do the non NP complete problem
part (the mapping part) on a digital computer.
There are papers saying (by researchers other than D-wave) that a
quantum computer can do what a digital computer cannot. So you can
never get digital computer hardware to emulate a quantum computer.
A quantum computer (forgot how many qubits but very small) can handle
10^300 states, which is more than the number of protons in the known
universe.
I also read an article, which says that a quantum computer is like
cold fusion ---- neither will happen.
galathaea
QP-solvable problems
( and the more technologically relevant BQP subcollection )
have not been shown to contain NP-complete problems
also
the D-Wave machines are allegedly hybrid architectures
with only a handful (16?) of qubits available
this only begins to allow a very restricted set of quantum simulations
which is where the money for quantum computing is right now
( molecular conformation and drug binding,
collision analyses and fusion,
... )
the banking industry will adapt to using complete encryption
techniques
as the need arises
but that is already doable without full quantum computing
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
Vend
> the banking industry will adapt to using complete encryption
> techniques
> as the need arises
> but that is already doable without full quantum computing
It is belived that as soon as a quantum computer with a significant
number of qubits (thousands) becomes available, asymmetric
cryptographic and key exchange algorithms such as RSA and Diffie-
Hellman will be practically broken, forcing organization to move to
other systems, possibly quantum key exchange protocols (that are
considered the most feasible application of quantum computing for
now).
era...@gmail.com
The D-wave computers played Sudoku in the demonstrations. How
difficult is that to program ?
Is Sudoku a good comparison with text-search, video search, bio-
informatics search ?
Thanks,
Erach
Vend
> Can quantum computers be used to design quantum computers ?
In principle, paper or clay tablets can be used to design anything
that is designable.
In practice, what do you mean?
> The D-wave computers played Sudoku in the demonstrations.
With 16 qubits?
> How
> difficult is that to program ?
Sudoku is NP-complete, but it's usually easly solvable by computer on
typical grid sizes.
> Is Sudoku a good comparison with text-search, video search, bio-
> informatics search ?
Besides the NP-completeness, I don't think so.
galathaea
> On 2 Mag, 22:03, galathaea <galath...@gmail.com> wrote:
>
> > the banking industry will adapt to using complete encryption
> > techniques
> > as the need arises
> > but that is already doable without full quantum computing
>
> It is belived that as soon as a quantum computer with a significant
> number of qubits (thousands) becomes available, asymmetric
> cryptographic and key exchange algorithms such as RSA and Diffie-
> Hellman will be practically broken,
that is the need i referred to
> forcing organization to move to
> other systems, possibly quantum key exchange protocols (that are
> considered the most feasible application of quantum computing for
> now).
i may be mistaken or out of date
but the only quantum key exchange protocols i am aware of
do not require full quantum computers
in other words
they don't require an ability to program qubits
and process them by a complete set of quantum gates
the ones i am aware of
had prototypes built (and some companies in production)
before any production quantum computers were available
just some fiber optics
some polarisers
and an ability to entangle transmissions
maybe i'd call that " quantum communication "
those may have a bright future
particularly as shor's algorithm becomes implementable
but i still think the big money in computing
is simple quantum simulation
drug companies
big energy
most of the others desirous of qc
like experimental mathematicians
have little money (relatively) to back their desires
of course
technology is extremely difficult to predict
it is possible a quantum algorithm for signal multiplexing
might re-revolutionise the internet and hosting...
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
era...@gmail.com
computer (Von-Neumann).
They run in pseudo-parallel or serially.
Now, on a 16 qUBit DWAVE System (which has been demonstrated) or a 7
bit IBM Quantum System (factored the number 15) ------ DO PSEUDO-
PARALLEL ALGORITHMS EXIST. Or does it have to be feed-forward
recursive neural net architectures.
Now, consider a feed-forward recursive pseudo-parallel algorithm for a
quantum computer (x Bit).
The x Bit's can emulate 10^300 or more states ---- or more protons
than there are in the known
Universe.
STEP1. You feed the problem.
STEP2. You get the first X bits of the output.
STEP 3. Go back to STEP 1 but feed in the problem and the first X bits
of the output.
STEP 4. You get the second X bits of the output.
STEP 5. Go back to Step 1 and feed in the problem with the first and
the second X bits of the output.
STEP 6. You get the third X bits of the output.
STEP 7. REPEAT STEPS above recursively and feed-forward until all the
bits of the output are got.
Best Regards,
Erach
On May 3, 2:52 am, Vend <ven...@virgilio.it> wrote:
Vend
> i may be mistaken or out of date
> but the only quantum key exchange protocols i am aware of
> do not require full quantum computers
>
> in other words
> they don't require an ability to program qubits
> and process them by a complete set of quantum gates
If by "full quantum computer" you mean an universal device capable of
manipulating qubits according to a stored program (a quantum
equivalent of an universal turing device), then you're right, they are
not needed.
Any algorithm can, in principle, be implemented in hardware.
In practice, depending on the application, it can be more or less
feasible.
With quantum cryptography you need a device that does always the same
simple task so there is no real need for it to be programmable.
> the ones i am aware of
> had prototypes built (and some companies in production)
> before any production quantum computers were available
>
> just some fiber optics
> some polarisers
> and an ability to entangle transmissions
Entanglement isn't needed in all protocols.
The minimal hardware you need is an higly controlled very faint
(possibly one photon at time) light source, polarizers and single-
photon detectors.
> maybe i'd call that " quantum communication "
Normally it's called "quantum information".
> those may have a bright future
> particularly as shor's algorithm becomes implementable
> but i still think the big money in computing
> is simple quantum simulation
Yes, and probably that will need a full programmable quantum computer.
> drug companies
> big energy
>
> most of the others desirous of qc
> like experimental mathematicians
> have little money (relatively) to back their desires
It can be hypothesized that quantum computers will also be extensively
applied to optimization problems due to the quadratic speed-up of the
Grover and related algorithms.
> of course
> technology is extremely difficult to predict
>
> it is possible a quantum algorithm for signal multiplexing
> might re-revolutionise the internet and hosting...
A world-wide network of system in a coherent state? Sound at least as
improbable as going to the Moon :D
Ralph Hartley
> Sudoku is NP-complete, but it's usually easly solvable by computer on
> typical grid sizes.
Sudoku is not NP-complete.
You are forgetting the rules that say that each puzzle has a unique
solution, which can be found without guessing.
I'm not sure *exactly* what that last condition means in mathematical
terms, but if means *anything* it rules out NP-completeness. Any
reduction of an NP-complete problem to Sudoku-like problems would
generate some puzzles that require guessing, and which therefore are not
valid Sudoku instances.
That may still hold even if P=NP. The exact wording of the rule may
vary. Does it permit puzzles that require either guessing or currently
unknown algorithms ?
Tha requirement for a unique solution (which is not ambiguous at all)
rules out NP-completeness as well. It isn't even a decision problem.
Ralph Hartley
era...@gmail.com
This is for those who are absolutely, absolutely, desperate and
medically required to lose weight.
Drink Urine (check urine therapy on the internet)
or eat ghee (clarified butter) 2 spoons in the morning (on waking up)
with one glass of water.
Both procedures cause diarrhoea and U lose weight.
Better than surgery ?
Consult your doctor.
Erach
era...@gmail.com
The banks can do face and speech recognition (quantum algorithms will
help them there, you do not need manual labor). This will also more
securely authenticate the transaction than any ENCryption algorithm.
Today there are enough computer resources with banks to save the
person's face / movie video /speech recognition .
Also, RSA encryption was done when computer resources were scarce.
****
And for eating ghee to cause diarrhoea to lose weight ----- you eat 2
teaspoons of ghee in the morning on an EMPTY STOMACH with one glass of
water. Keep your stomach empty for half an hour.
Erach
tc...@lsa.umich.edu
Ralph Hartley <har...@aic.nrl.navy.mil> wrote:
>Sudoku is not NP-complete.
>
>You are forgetting the rules that say that each puzzle has a unique
>solution, which can be found without guessing.
I've encountered Sudoku puzzles with more than one solution, albeit in very
special contexts. In an MIT Mystery Hunt a couple of years ago, there was
a Sudoku puzzle (then called Number Place) with exactly two solutions. The
Mystery Hunt, however, is for hard-core puzzle fanatics and is notorious for
devious and nonstandard puzzles. It's fair enough to rule out these
exceptions and say that Sudoku has to have a unique solution.
On the other hand, "can be found without guessing" is certainly not
a requirement. In the World Sudoku Championship, for example, at least
as of a year or two ago, the final puzzle required guessing. There have
been complaints about this, although the complaints have *not* been that
a puzzle that requires guessing violates the rules, but that such a
problem does not do such a good job of discriminating between the
abilities of top solvers (at least if only one such puzzle is provided,
as opposed to a whole slew of them). The winner will be whoever makes
the luckiest guess, not necessarily the best solver.
"No guessing" is a widely held *aesthetic* value, but it has never been a
*rule*.
>I'm not sure *exactly* what that last condition means in mathematical
>terms,
Indeed, it's difficult to make this precise. Probably it is best formalized
as some kind of stringent space bound---logspace? Constant space?
>Tha requirement for a unique solution (which is not ambiguous at all)
>rules out NP-completeness as well. It isn't even a decision problem.
The requirement for a unique solution is essentially equivalent to a
decision problem with a promise: Given an instance which is guaranteed to
have at most one solution, does it have a solution? If you can solve this
problem, then you can solve a Sudoku instance one blank at a time.
Conversely, if you can solve Sudoku, then you can solve this decision
problem.
An old result of Valiant and Vazirani ("NP is as easy as detecting unique
solutions") shows that this promise problem cannot be solved in randomized
polynomial time (RP) unless RP = NP. Essentially the argument is that if
you have an arbitrary NP problem then you can add random constraints that
are linear over F_2 (the field with two elements) to bring down the number
of solutions to one (if there are any at all) with high probability, and
thus "randomly reduce" the NP problem to the above promise problem. So
this is a sort of "weak NP-completeness" result.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Vend
> Vend wrote:
> > Sudoku is NP-complete, but it's usually easly solvable by computer on
> > typical grid sizes.
>
> Sudoku is not NP-complete.
I'm not a Sudoku player, I took that information from the Wikipedia,
that can be wrong of course.
It says that Sudoku is NP-complete in the size of the board.
> You are forgetting the rules that say that each puzzle has a unique
> solution, which can be found without guessing.
>
> I'm not sure *exactly* what that last condition means in mathematical
> terms, but if means *anything* it rules out NP-completeness. Any
> reduction of an NP-complete problem to Sudoku-like problems would
> generate some puzzles that require guessing, and which therefore are not
> valid Sudoku instances.
>
> That may still hold even if P=NP. The exact wording of the rule may
> vary. Does it permit puzzles that require either guessing or currently
> unknown algorithms ?
I don't understand what do you mean here.
Any NP-complete problem can be solved without guessing. Some NP-
complete problems have unique solutions.
A problem is defined NP if there exists one algorithm that tests
whether a candidate solution is valid in asymptotically polynomial
time in the size of the problem instance.
A problem is defined NP-complete if it's NP and any other NP problem
can be polynomially reduced to it.
> Tha requirement for a unique solution (which is not ambiguous at all)
> rules out NP-completeness as well. It isn't even a decision problem.
It can be formulated as a decision proble as: "is there a solution for
this puzzle?"
> Ralph Hartley
un.st...@gmail.com
> On 5 Mag, 05:28, Ralph Hartley <hart...@aic.nrl.navy.mil> wrote:
>
> > Vend wrote:
> > > Sudoku is NP-complete, but it's usually easly solvable by computer on
> > > typical grid sizes.
>
> > Sudoku is not NP-complete.
>
> I'm not a Sudoku player, I took that information from the Wikipedia,
> that can be wrong of course.
> It says that Sudoku is NP-complete in the size of the board.
If I remember correctly the generalised sudoku is NP-complete but if
we require that it has only one solution and it can be solved by
reasoning, as is the case in normal sudoku puzzles, then it can be
solved in polynomial time.
Patricia Shanahan
> On 5 Mag, 05:28, Ralph Hartley <hart...@aic.nrl.navy.mil> wrote:
>> Vend wrote:
>>> Sudoku is NP-complete, but it's usually easly solvable by computer on
>>> typical grid sizes.
>> Sudoku is not NP-complete.
>
> I'm not a Sudoku player, I took that information from the Wikipedia,
> that can be wrong of course.
> It says that Sudoku is NP-complete in the size of the board.
>
>> You are forgetting the rules that say that each puzzle has a unique
>> solution, which can be found without guessing.
>>
>> I'm not sure *exactly* what that last condition means in mathematical
>> terms, but if means *anything* it rules out NP-completeness. Any
>> reduction of an NP-complete problem to Sudoku-like problems would
>> generate some puzzles that require guessing, and which therefore are not
>> valid Sudoku instances.
>>
>> That may still hold even if P=NP. The exact wording of the rule may
>> vary. Does it permit puzzles that require either guessing or currently
>> unknown algorithms ?
>
> I don't understand what do you mean here.
> Any NP-complete problem can be solved without guessing. Some NP-
> complete problems have unique solutions.
I think what is meant by "without guessing" may be equivalent to
"without backtracking". I'm a sudoku beginner, not a skilled solver, so
I have two approaches:
1. Deduce the correct value for a currently blank cell from the rules
and the values in the non-blank cells and fill it in.
2. Deduce that a cell must contain one of a small set of values, and
pick one. Go with that choice until it either results in a complete
solution, or results in a cell having no correct value. If it fails,
backtrack and fill in an alternative.
I've noticed that as I've got better at sudoku, the proportion of
problems I solve using only approach #1 increases. I suspect that many,
or even all, of the puzzles I've looked at could be solved, with
sufficient skill, using only approach #1.
The time to solution using approach #1 depends only on skill, not luck.
There is random element in approach #2. It will take longer, with the
same level of skill, if the random pick is wrong.
Patricia
tc...@lsa.umich.edu
Vend <ven...@virgilio.it> wrote:
>I'm not a Sudoku player, I took that information from the Wikipedia,
>that can be wrong of course.
>It says that Sudoku is NP-complete in the size of the board.
If by Sudoku one means the problem of deciding whether a partially filled
n^2 x n^2 grid has a legal completion, then Sudoku is NP-complete.
The objection that is being raised is that a more accurate description of
Sudoku would be the problem of *finding* a legal completion of a partially
filled n^2 x n^2 grid, *given* that there exists a unique solution. This
is a subtly different problem, and there's no straightforward way to
convert it into an NP-complete decision problem. The issue of finding
vs. deciding is not so hard to get around, but the promise of a unique
solution means that you need the framework of promise problems, which the
usual definition of NP can't cope with very well.
>Any NP-complete problem can be solved without guessing.
By "without guessing" is meant that the problem can be solved by a
successive application of a fixed set of "rules" or simple logical
inferences, where the ruleset does not allow backtracking searches
of arbitrary length. Many Sudoku problems have this property, though
not all.
>Some NP-complete problems have unique solutions.
You probably mean to say that some *instances* of NP-complete problems have
unique solutions, which is different from saying that some NP-complete
problems have the property that *all* problem instances have a unique
solution.
Vend
> In article <1178378816.130017.87...@o5g2000hsb.googlegroups.com>,
>
> Vend <ven...@virgilio.it> wrote:
> >I'm not a Sudoku player, I took that information from the Wikipedia,
> >that can be wrong of course.
> >It says that Sudoku is NP-complete in the size of the board.
>
> If by Sudoku one means the problem of deciding whether a partially filled
> n^2 x n^2 grid has a legal completion, then Sudoku is NP-complete.
>
> The objection that is being raised is that a more accurate description of
> Sudoku would be the problem of *finding* a legal completion of a partially
> filled n^2 x n^2 grid, *given* that there exists a unique solution. This
> is a subtly different problem, and there's no straightforward way to
> convert it into an NP-complete decision problem. The issue of finding
> vs. deciding is not so hard to get around, but the promise of a unique
> solution means that you need the framework of promise problems, which the
> usual definition of NP can't cope with very well.
Ok.
> >Any NP-complete problem can be solved without guessing.
>
> By "without guessing" is meant that the problem can be solved by a
> successive application of a fixed set of "rules" or simple logical
> inferences, where the ruleset does not allow backtracking searches
> of arbitrary length. Many Sudoku problems have this property, though
> not all.
Backtracking is one technique. There are others, not necessarly more
efficient. You can simply generate random solutions and check for
validity, and you would solve the instance with probability 1.
> >Some NP-complete problems have unique solutions.
>
> You probably mean to say that some *instances* of NP-complete problems have
> unique solutions, which is different from saying that some NP-complete
> problems have the property that *all* problem instances have a unique
> solution.
Yes.
Chris F Clark
> By "without guessing" is meant that the problem can be solved by a
> successive application of a fixed set of "rules" or simple logical
> inferences, where the ruleset does not allow backtracking searches
> of arbitrary length. Many Sudoku problems have this property, though
> not all.
This reminds me of the "Compiler Writer's Full Employment Theorem"
which states something akin to "for any fixed set of rules there is
always at least one element not expressible by the rules, so there is
always one extension to the set of rules to cover that case." Please
excuse my poor memory for the loose recollection of the exact
phrasing, but in context this seems even more apt.
I believe what you are saying is that for any set of rules (theorems
or problem sovling tricks) that solve any n*n fixed sized Sudoku
problem, there is a larger n+k*n+k problem that needs atleast one
additional rule (theorem, problem solving trick). I would interpret
this as meaning that any fixed sized rule can only resolve the
interdepence of a fixed number of interelated cells, so to make the
bigger problem, one needs a larger set of cells to express a larger
cycle of interelated cells, so that the cycle is large enough to
exceed the rules previously defined. (more on this below)
However, I wonder about the truth of that. Isn't there a way of
solving systems of logical equations based upon Gauss-Jordan
elimination that operates in n**3 time where n is the number of
variables and also the number of simultaneous equations that need to
be solved (that is there is one equation per variable? If so,
couldn't one encode the Sudoku problem as the appropriate set of
logical equations and run said algorithm. What am I missing from
that? That is, why does said technique not work? Is my memory of the
existance of such an algorithm wrong? Or does it have requirements
that are not met by the type of logic problems that are not met by a
Sudokyu puzzle translation? Or perhaps somehow the problem size grows
eponentially in the n we usually use to measure Sudoku problems?
Otherwise, as I understand it, Gaussian elimination does not require
"guessing". You mechanically manipulate the problem until you have a
sequence of problems where each variable depends only on the solution
of preceeding variables, and one variable depends solely on the
combination of constants. You then calculate that first variable and
use it by back-susbtitution to solve all the remaining variables.
Do the manipulations required to do this kind of elimination require
properties (e.g. the existance of inverses) that are not provided by
the structure of logical variables (i.e. we have only a ring and we
need a field or something)?
Not that I intend to start solving Sudoku puzzles by Gaussian
Elimination (rather than by learning new solution rules), but I still
want to know.....
(the more below part)
Even if there were not a Gaussian Elimination method, for any fixed
sized set of problems, there would still be a complete set of rules
sufficient to solve those problems without "guessing". And, I would
be surprised if that were not true, at worst one would have to devise
(a possibly large) set of exception patterns that one would
"memorize". For any fixed (finite) problem size that set would be
guaranteed to be finite.
To make this concrete, the solutions to any fixed sized set of Sudoku
problems forms a regular language. If you have a problem that
corresponds to a unique solution, there must be a unique element of
the regular language that matches that and one would be able to write
a regular expression (and thus a determinstic finite state automata)
that computes that unique element of the regular language. (That may
not be an ideal way of solving the problem, but it would work and
would never "guess".)
This does not contradict the more general, unbounded Sudoku problem
being NP-complete. I have no reason to believe that the set of
solutions to the general problem forms a regular language (and I'm
certain it doesn't). It just says you can take any subset of that
problem and solve it without guessing by learning enough "rules".
Thus, any 9x9 problem (or 16x16) or whatever sized problem can be
solved without guessing, but knowing how to solve one sized problem
will still leave you with some problems of a larger size that you
might not be able to solve. That is "the Sudoku Players Full Enjoyment
Theorem" (smile).
-Chris
*****************************************************************************
Chris Clark Internet : com...@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
tc...@lsa.umich.edu
Chris F Clark <c...@shell01.TheWorld.com> wrote:
>I believe what you are saying is that for any set of rules (theorems
>or problem sovling tricks) that solve any n*n fixed sized Sudoku
>problem, there is a larger n+k*n+k problem that needs atleast one
>additional rule (theorem, problem solving trick).
I didn't say this. However, what you say here is plausible.
>However, I wonder about the truth of that. Isn't there a way of
>solving systems of logical equations based upon Gauss-Jordan
>elimination that operates in n**3 time where n is the number of
>variables and also the number of simultaneous equations that need to
>be solved (that is there is one equation per variable?
A set of linear equations over a finite field can be solved in the manner
you describe here. In particular, if your "logical equations" are limited
to using the operations XOR and NOT then you're fine. Unfortunately, once
you allow AND or OR as well, this method breaks down. There isn't any known
way to express the existence of a completion to a partially filled Sudoku
grid using just XOR and NOT without AND or OR; if there were, then P would
equal NP.
>Otherwise, as I understand it, Gaussian elimination does not require
>"guessing".
It certainly doesn't require backtracking searches of the type that people
usually have in mind when they use the term "guessing." But if you could
construct a problem which couldn't be solved by "simple" logical inferences
and seemed to require Gaussian elimination, I suspect that most solvers
of the "no guessing" school would be unhappy. Doing Gaussian elimination
by hand is a pretty painful process requiring lots of scratch paper and
careful organization; you'd probably be better off in practice doing a
backtrack, and so people would still probably say that the problem requires
guessing. This is the sort of difficulty you encounter if you try to make
the term "guessing" mathematically precise.
>Even if there were not a Gaussian Elimination method, for any fixed
>sized set of problems, there would still be a complete set of rules
>sufficient to solve those problems without "guessing". And, I would
>be surprised if that were not true, at worst one would have to devise
>(a possibly large) set of exception patterns that one would
>"memorize". For any fixed (finite) problem size that set would be
>guaranteed to be finite.
That is true in principle. However, even for ordinary 9x9 Sudoku, there
is no known set of rules (or rules + exceptions) of manageable size that
covers all possibilities, if you don't allow backtracking (or something
effectively equivalent to backtracking). The no-guessing-allowed folks
are not going to be happy if you say, "Just learn these 25 rules and
13.7 billion exceptions and you'll never have to guess."
For example, Google "minimum Sudoku" to find examples of Sudoku grids with
only 17 entries. Tens of thousands of examples are known. Challenge: come
up with a humanly manageable set of rules+exceptions that allow you to solve
all of these "without guessing" in some reasonable sense of the term.
Chris F Clark
> That is true in principle. However, even for ordinary 9x9 Sudoku, there
> is no known set of rules (or rules + exceptions) of manageable size that
> covers all possibilities, if you don't allow backtracking (or something
> effectively equivalent to backtracking). The no-guessing-allowed folks
> are not going to be happy if you say, "Just learn these 25 rules and
> 13.7 billion exceptions and you'll never have to guess."
>
> For example, Google "minimum Sudoku" to find examples of Sudoku grids with
> only 17 entries. Tens of thousands of examples are known. Challenge: come
> up with a humanly manageable set of rules+exceptions that allow you to solve
> all of these "without guessing" in some reasonable sense of the term.
Thanks, I'll look into it. I suspect that the number of exceptions
depends on the number of rules, but I would be surprised if it worked
out like the four-color map problem, where the "finite" number of
rules and exceptions were beyond simple human understanding and
required a program to verify. On gthe other hand, I also wouldn't be
surprised the other way either, say that there a set of 81 rules that
were sufficient to handle all the cases but for a small hand-full (say
another 81) exceptions. I wouldn't want to memorize those sets, but I
bet someone could.
era...@gmail.com
Applied Research only --- salary (from another source I got of a
senior researcher in India is) Rs 20 lakhs to Rs 40 lakhs. that is
about 50,000 US Dollars to 100,000 USDollars.
Should know Grid Computing (who knows it), parallel computing (who
knows it), video recognition (to remove pornography I guess), text
databases, and so on.
You can do what you want.
But you won't get the second interview if you say you are interested
in quantum computing and can prove that is not basic research. Of
course, you should say you know grid computing and video recognition
and image recognition and parallel computing and so on -------------
when that is not mentioned in your resume.
So are they looking for a researcher or what.
In Motorola, the (stupid, free-thinking) researchers are kept seperate
from the production organization because they come up with (dangerous)
ideas.
3M comes up with great idea.
California is full of nuts who come up with great ideas.
Now, Bangalore wants to do research ------------- but the know-alls
from California (worked for 3 months at IBM Research, Almaden) do not
want somebody smarter than them.
So ---- you do research ---- but you don't want a researcher --------
you want a conformist.
*************
In the Soviet Union, what happenned ?
Erach
Erach
era...@gmail.com
about a Turing machine which can solve a hard problem that could be
solved by a quantum machine ---------------- only if it was provided
with a "randomizer".
Pray how will you write a "randomizer" on a Turing machine.
So that demonstrates that a quantum machine is more powerful than a
randomizer.
NOW ---------- STUDY THE WORD "convolution" on Wikipedia.
Convolution is the multiplication of a long periodic discrete Fourier
series (can be continuous) by a shorter fourier series.
Now, that word convolution does not appear in Shor's algorithm. I
studied convolution either in my under graduate school (IIT Mumbai) or
in my graduate MS/PhD (University of Minnesota, Minneapolis).
Using the word convolution you will get several more important results
of Fourier Series.
I do not know about factorization of prime numbers using Shor's
algorithm.
But for picture processing, video processing, image processing,looking
up text databases, sorting text databases ---------you can feed in the
"KERNEL" as a smaller known fourier series ------- and extract the
entire known series.
This can happen only if the known series --- existed in the "memory"
of the quantum computer, proving that the whole world is "known" in
several dimensions.
Erach (desperately looking for a USD 100,000 job in Yahoo Research,
Bangalore but the interviewer does not want a researcher to have
original ideas --- he wants a conformist I think).
>
>
> > Ralph Hartley- Hide quoted text -
>
> - Show quoted text -
era...@gmail.com
functions) on wikipedia.
To extract a full-picture (maybe not prime number ) you send in part
of the answer (or a kernel of truth) to pull out the whole answer.
Shor's algorithm (I think) describes convolution even though he does
not use that word.
You will get lots of results and theories if you study convolution.
Erach
Douglas Eagleson
> D-Wave Inc. (I read in the various news articles on the net)
> has demonstrated a quantum computer (and for sceptics, there are
> several technical articles in little-known journals, so says the web)
> and is planning to give free accounts to program a quantum computer.
>
>
> This should be great for PhD hunters.
>
> Erach
>
> Contact
>
> D-Wave Systems Inc.
> 100 - 4401 Still Creek Drive
> Burnaby, British Columbia
> Canada
> V5C 6G9
>
> Telephone: (604) 630-1428
> Fax: (604) 630-1434
>
>
> For media inquiries: m...@dwavesys.com
>
> For investor inquiries: inves...@dwavesys.com
>
> For scientific and technical inquiries: techni...@dwavesys.com
>
> For all general inquiries: i...@dwavesys.com
>
> On May 2, 4:58 am, John Ladasky <lada...@my-deja.com> wrote:
>
>
>
> > On Apr 28, 10:40 pm, "erac...@gmail.com" <erac...@gmail.com> wrote:
>
> > > Hi all,
> > > Is it time yet to start a seperate newsgroup on USENET "comp.quantum-
> > > computers"...
> > [snip]
> > > ps. Please send me votes YES or NO which I can submit to the USENET
> > > authorities to start a comp.quantum-computers newsgroup
>
> > Erach,
>
> > I submit to you, simultaneously, one "yes" vote and one "no"
> > vote. :^P
>
> > +-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
> > | Ladasky Home Solar, Inc.: blowing sunshine up your |
> > | power grid since March 24, 2005. Fiat lux! |
> > +-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
> > | Uptime Downtime kWh generated kWh consumed |
> > | 765.5 days 13 hours 13341 14738 |
> > +-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+- Hide quoted text -
>
> - Show quoted text -
Startup companies are interesting places to interact with.
They have to perform to get the next batch of money.
A product called a quantum computer as architecture appears the
trend. And to make the data bus a non issue and have only a memory
state design issue is a good thing. BY focusing on only memory, a
custom chip may be allowed to cause the quantum computer. Memory in
the cpu must also be quantum state type.
Connection between memory were either new or old common conventional
style!
And to get the product a compromise was the issue. Get the little
chips.
So the interface between qubit state and implanted silicon state was
an issue. A design??????
A density advantage someday is the prediction. A silicon CPU with
chips of qubits!!!! It gets a real product.
tc...@lsa.umich.edu
<depends on the number of rules, but I would be surprised if it worked
<out like the four-color map problem, where the "finite" number of
<rules and exceptions were beyond simple human understanding and
<required a program to verify. On gthe other hand, I also wouldn't be
<surprised the other way either, say that there a set of 81 rules that
<were sufficient to handle all the cases but for a small hand-full (say
<another 81) exceptions. I wouldn't want to memorize those sets, but I
<bet someone could.
If you could reduce 9x9 Sudoku to a set of 81 non-backtracking, non-guessing
logical rules plus 81 exceptions, that would be a major achievement that
would earn you worldwide fame. There is a good chance that such an
accomplishment would be a major step towards showing that P = NP.
By the way, the Robertson-Sanders-Seymour-Thomas version of the 4-color
theorem uses only 32 "rules" and 633 "configurations," which is not totally
beyond human understanding (though the analogy with Sudoku "rules" and
"exceptions" is pretty loose). Note that 4-coloring a planar map can be
done in polynomial time.
era...@gmail.com
I have a very short email from Peter Shor (the writer of Shor's
algorithm) who says that convolution is good for quantum computers but
it was NOT needed for factorization.
Just study convolution in wikipedia.
Erach
Albert van der Horst
<tc...@lsa.umich.edu> wrote:
<SNIP>
I really can't see that having a unique solutions has anything to
do with NP-completenes.
Let us take the following version of the travelling salesman problem.
The N*(N+1) distance are algebraically independent.
This guarantees that all paths that can be travelled are different,
so the solution is unique.
If this could be solved in polynomial time I would say all TV-problems
can be solved in polynomial time by shifting the distances over a
suitable small distance to make them algebraically independent.
>--
>Tim Chow tchow-at-alum-dot-mit-dot-edu
Groetjes Albert
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
tc...@lsa.umich.edu
Albert van der Horst <alb...@spenarnc.xs4all.nl> wrote:
>I really can't see that having a unique solutions has anything to
>do with NP-completenes.
>
>Let us take the following version of the travelling salesman problem.
>The N*(N+1) distance are algebraically independent.
>This guarantees that all paths that can be travelled are different,
>so the solution is unique.
>
>If this could be solved in polynomial time I would say all TV-problems
>can be solved in polynomial time by shifting the distances over a
>suitable small distance to make them algebraically independent.
This is all correct.
It doesn't, however, contradict anything that I said about Sudoku. You
correctly observe that an algorithm for solving TSP instances for which we
are promised a unique optimal tour can be easily converted into an algorithm
for solving *any* TSP instance. This does not mean that an algorithm for
solving Sudoku instances for which we are promised a unique solution can
be easily converted into an algorithm for solving Sudoku instances that
don't carry such a promise.
The usual reductions between NP-complete problems aren't always
"parsimonious" (meaning that they preserve the *number* of solutions).
Hence different NP-complete problems may behave differently with respect
to the issue of unique solvability.
era...@gmail.com
programs for a quantum computer.
An "small" qubit (say 7 or 16) in order to be perfect has so many
error-correcting gates that there is lots of wastage.
How does the human brain or the dogs brain or a bacterial brain
compute in the presence of biological imperfection ?
Can we design "distributed / fault-tolerant" software using say neural-
networks, distributed algorithms, genetic algorithms, distributed
theorem provers for quantum machines that would save on the number of
gates used to implement qubits.
Erach