Second Clay Mathematics Award claimed, but how should it be split?
Future_News
by a stunning triple development which has finally solved its most
famous problem: whether P=NP. This was one of the seven problems for
which the Clay Mathematics Institute offered a million dollars in
their famous Millennium Meeting over thirty years ago, and the second
(after the Poincaré conjecture) to be solved. However, a controversy
has erupted over how the prize money (which ten years ago was
increased to two million dollars) should be distributed.
What does the statement `P=NP' mean? A good way to understand it is to
look at an illustrative example. Suppose I secretly choose two prime
numbers p and q, tell you their product n=pq and ask you to tell me
what p and q are. In principle you can work this out, since by the
fundamental theorem of arithmetic p and q are uniquely determined.
However, in practice it is not easy to come up with a systematic way
of finding them other than to look at all primes up to n1/2 and see
whether they are factors of n. If n has 500 digits, this takes much
too long to be feasible on even the fastest computers, and this
difficulty is the basis of much of modern cryptography. Actually, more
efficient methods have been discovered than straightforward trial and
error, but, even after decades of intensive research, it is still out
of the question to factorize a 500-digit number. At the end of the
last century there was a great deal of excitement when Peter Shor
discovered that quantum computers could factorize large numbers far
more efficiently, but, despite several well-publicized announcements
to the contrary, nobody has managed to build such a computer.
However one looks at it then, factorizing large numbers is not easy.
However, the following related problem is much much easier: I choose
p, q and n and ask you whether n=pq. All you have to do to answer this
problem is a boring long multiplication, and if you are careful, or
use a computer, you can do this quickly and accurately. Thus, although
it looks hard to find p and q, it is much easier to check whether pq=n
once p and q have been found.
There are many other problems in computer science of a similar nature.
They ask you to find an object with certain properties, and while this
looks extremely hard, it is easy to check whether a given object has
the required properties. One interesting example is the following: I
give you a mathematical statement S and ask you to find a proof of S
of under a certain length (written in a formal language of your
choice). One of the great fascinations of mathematics is that it is
(in principle anyway) far easier to check whether a proof is correct
than it is to find the proof in the first place.
The statement `P=NP' is roughly speaking the extraordinary claim that
when a property is easy to check, it is also easy to determine whether
any object has the property. Thus, if P=NP, then from the fact that
long multiplication is easy it would follow that factorizing large
numbers was easy, and from the fact that proofs are easy to check it
would follow that they are easy to find. Despite the strongly
counterintuitive nature of these conclusions, they are now known to be
true - but with qualifications which will be described below.
As mentioned above, this breakthrough came in three stages. First, in
a little known paper of 2019, Yuri Kolpakov, a Russian topologist,
found a higher-dimensional generalization of Frank's celebrated knot-
untying algorithm of three years earlier. Following Frank's general
scheme, Kolpakov showed that, given a hypersurface in Rn, one could
associate with it a graph with edge-weights belonging to a certain
ring. It was then possible to prove that the hypersurface was knotted
if and only if the graph had a property which, by a generalization of
classical results of Robertson and Seymour, was equivalent to the non-
existence of certain weighted subgraphs known as forbidden proper
minors. Testing for these can be done in polynomial time.
The technical details need not concern us here, but one point is worth
noting. The proof of Robertson and Seymour does not actually provide
the forbidden minors: it merely proves indirectly that they exist. The
same applies to the generalization. Consequently, Kolpakov's proof,
like Frank's before him, does not actually give any bound on the
degree of the polynomial which itself bounds the time taken by his
algorithm.
The second step was made two years ago by Jane Nichols, a graph
theorist at Yale. She was studying the computational complexity of
certain problems in graph theory, and while doing so discovered a
complicated property of graphs, again with weights in certain rings,
which she called, ironically in the light of later developments,
`pseudo-twistedness'. She showed that this property was NP-complete.
This, in brief, means that if an efficient algorithm could be found
for discovering whether a graph was pseudo-twisted, then P would equal
NP. Like almost everybody else, Nichols took this as convincing
evidence that detecting pseudo-twistedness was intractable, and moved
on to other research. Her paper also received little attention, and it
is interesting to speculate why this was. It has been suggested that
the phrase `pseudo-twisted' was somehow off-putting to most
mathematicians, causing them to believe that Nichols's research was
not well motivated, though in a recent paper, she has explained the
very interesting line of thought, originating in theoretical physics,
that led her to her definition.
Nichols gave several talks on her work, including a colloquium at MIT,
which was attended by Mike Stearns, a young topologist who had been
studying the work of Kolpakov. As he put it later:
As the talk progressed, an idly outrageous thought occurred to me
- wouldn't it be amusing if Kolpakov's untwisting algorithm could
detect Nichols pseudo-twistedness of graphs? At first I chuckled
inwardly - but then I began to feel the hairs on the back of my neck
standing on end. I skipped the tea after the talk and rushed back to
my apartment, where I stayed until I more or less collapsed into bed
at 4am. I got up the next morning feeling totally sure that there must
be a mistake, but everything seemed to check out.
What Stearns had done was to find a `polynomial reduction' from
Nichols's problem to Kolpakov's. That is, in effect he devised an
efficient algorithm for transforming a graph into a high-dimensional
analogue of a knot diagram, in such a way that the graph was pseudo-
twisted if and only if the `knot diagram' was genuinely knotted.
Kolpakov's powerful algorithm could thus be used to determine whether
graphs were pseudo-twisted, even though this had been shown by Nichols
to be an NP-complete problem.
Stearns's initial reaction was to go out and celebrate, but soon
things were to turn sour.
At first I was disbelieving. Then, after a few days of careful
checking, I convinced myself that the argument was sound. I then wrote
it up quickly and asked one or two colleagues to check the details
themselves. Unfortunately, word got out about what was going on, and I
suddenly found myself at the receiving end of a whirlwind of
attention, most of it unwelcome. People started to say that my
contribution to the problem was trivial: essentially nothing more than
putting two pre-existing pieces of work together. But if that was all
it took, then why didn't Nichols solve the problem two years ago?
Here is Nichols's view of the matter.
Yes, Stearns deserves credit for noticing that Kolpakov and I had,
between us, proved that P=NP, but no, his reduction is not a difficult
piece of mathematics. The way I like to look at it, the proof that
P=NP comes in two parts, Kolpakov's polynomial-time algorithm and my
proof of NP-completeness. It is not quite trivial that these apply to
equivalent problems, and I fully admit that I did not recognise the
importance of what I had done. Nevertheless, I think Stearns's
achievement was one that would have been made by whoever was the first
person to think of trying it. Certainly, as soon as I heard what he
had done, I was able to come up with a reduction myself without seeing
his preprint.
Don Jackson, one of Stearns's colleagues at MIT, hotly disputes this
version of events.
Nichols is understandably bitter that she was not the person who
solved the P=NP problem. However, the fact remains that if Stearns had
not existed, then it would almost certainly still be unsolved today.
Sometimes in mathematics, it is not the technical achievement that
matters, but the courage and vision to ask the big questions.
What of Kolpakov? He has been keeping his own counsel so far, but one
can well imagine his reaction at hearing that he is likely to share a
prize of two million dollars. The decision about how to split the
money is made by the scientific committee of the Clay Mathematics
Institute. When we contacted a representative yesterday, she said:
The prize will not be awarded until the result is published in a
reputable journal, and a committee, which is yet to be formed, has
deemed it to be correct. This process will take at least two years,
and until then the Institute has no comment about how the prize will
be shared.
Leaving aside the question of the exact apportioning of credit, and
surely all three mathematicians deserve our huge admiration for this
remarkable achievement, what is the significance for mathematics and
computer science? Here again there is a wide divergence of opinion.
Jim Davies, a computer scientist at Stanford, believes that the
importance of the P=NP problem has been exaggerated.
So there's a polynomial time algorithm for factorizing integers,
proving theorems, finding Hamilton cycles etc. And then what? The
degree is not just large, it is unknown. Probably if it was known then
it would be enormous. Even an n10 algorithm is useless for practical
purposes. So nobody's going to be put out of business just yet.
Don Jackson disagrees.
This is the beginning of the end. Even if the algorithm isn't
practical, it delivers a shattering psychological blow to the
mathematical community. We may still be better than computers at doing
mathematics, but we are not that much better . In any case, now that
the existence of an algorithm is known, the hunt is on for an explicit
example. Historical precedent and the enormous commercial implications
of being able to solve NP-complete problems suggest that this story is
set to run and run.
Only time will tell. Meanwhile, if you are struggling to prove a
theorem, you'd better hurry up if you want to get there before some
clever computer programmer does it first.
OwlHoot
>
> [..]
Nice wind up ;-)
I fell for it hook line and sinker, even speed reading that year
as 2009. The author's posting nick should have been a giveaway too!
Mind you, I very much doubt things will turn out like that: P = NP
and similar problems have "undecidable" painted all over them IMHO.
Failing that, someone will prove that P and NP problems are disjoint
but there are types arbitrary close to each other, with a suitable
measure, so that there isn't a sharp dividing line (although in
that case the outcome would still be P <> NP fair and square).
But don't take my opinion as gospel, or anything like, as I'm fairly
clueless about all this!
Cheers
John Ramsden
Aatu Koskensilta
> Mind you, I very much doubt things will turn out like that: P = NP and
> similar problems have "undecidable" painted all over them IMHO.
Why is that?
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon mann nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Gordon Stangler
> OwlHoot <ravensd...@googlemail.com> writes:
> > Mind you, I very much doubt things will turn out like that: P = NP and
> > similar problems have "undecidable" painted all over them IMHO.
>
> Why is that?
>
> --
>
> "Wovon mann nicht sprechen kann, darüber muss man schweigen"
> - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Yes, why must they be undecidable? This is a very deep problem, and
like most deep problems, I feel in my gut that they MUST have a
solution. I am of the opinion that P != NP. There are simply too
many classes of exotic problems for them all to have one optimal class
of solutions. That is, they are not all solvable in polynomial time,
no matter what they polynomial exponent is.
James Waldby
...
> The second step was made two years ago by Jane Nichols, a graph theorist
> at Yale. She was studying the computational complexity of certain
> problems in graph theory, and while doing so discovered a complicated
> property of graphs, again with weights in certain rings, which she
> called, ironically in the light of later developments,
> `pseudo-twistedness'. She showed that this property was NP-complete.
There's a slight problem regarding facts in the above paragraph. Jane
Nichols is *not* a graph theorist at Yale, she teaches Clown there.
Ref. <http://www.clownlink.com/2007/10/jane-nichols.html>. This is
not to take away from the achievement, merely to set the facts straight.
> Nichols gave several talks on her work, including a colloquium at MIT,
> which was attended by Mike Stearns, a young topologist who had been
> studying the work of Kolpakov.
Some recent work of Stearns re "symbolic structures" and "symbolic
overlays" is referenced at <http://www.michaelstearns.com/>.
...
> Nichols is understandably bitter that she was not the person who
> solved the P=NP problem. However, the fact remains that if Stearns had
> not existed, then it would almost certainly still be unsolved today.
> Sometimes in mathematics, it is not the technical achievement that
> matters, but the courage and vision to ask the big questions.
...
--
jiw
:)
Future_News
Thank you for your good spirited replies. I think the solution must be
perhaps two fold playing on the duality of function between software
and hardware.
Here is a loose schematic of this 'future' news idea: and the
'twisted' nature of it:
Architectural partition for a 100 GbE link
Media Access Control (MAC)
Reconciliation Sublayer
Physical Coding Sublayer (PCS)
Physical Medium Attachment (PMA)
Physical Medium Dependent (PMD)
Media Independent
Interface (MII)
P
h
y
s
ic
a
l M
e
d
iu
m
D
e
p
e
n
d
a
n
t (P
M
D
)
P
h
y
s
ic
a
l M
e
d
iu
m
A
tta
c
h
m
e
n
t2
(P
M
A
2 )
100 GbE
Optical Module
P
h
y
s
ic
a
l M
e
d
iu
m
D
e
p
e
n
d
a
n
t (P
M
D
)
P
h
y
s
ic
a
l M
e
d
iu
m
A
tta
c
h
m
e
n
t2
(P
M
A
2 )
100 GbE
Optical Module
P
a
c
k
e
t In
te
rfa
c
e
M
e
d
ia
A
c
c
e
s
s
C
o
n
tro
l (M
A
C
)
P
h
y
s
ic
a
l C
o
d
in
g
S
u
b
la
y
e
r (P
C
S
)
P
h
y
s
ic
a
l M
e
d
iu
m
A
tta
c
h
m
e
n
t1
(P
M
A
1 )
100 GbE
ASIC
P
a
c
k
e
t In
te
rfa
c
e
M
e
d
ia
A
c
c
e
s
s
C
o
n
tro
l (M
A
C
)
P
h
y
s
ic
a
l C
o
d
in
g
S
u
b
la
y
e
r (P
C
S
)
P
h
y
s
ic
a
l M
e
d
iu
m
A
tta
c
h
m
e
n
t1
(P
M
A1 )
100 GbE
ASIC
n
n
m
simple striping of 66-bit blocks
Toapearin: RedwodNCeituy,rCaAAl.WnAeedidgteisnaodnr-
&cWheNsDil.teeyeGpcPeartursutbhmleirnseehMfenisnltidgcfoh
(ofaEreCdlsot.C)
me,.mpPMureptodeziorcetrrSinacgiletnshceeeqfu&utuerenacnedpunrdoercsteasnsdiinnggthepast.
IpresentageneraltaxonomIynoBsftUointuenuulFidtrveeaeeblrron,rsfAueiCttCabyOarsorytocgrhfn8aiCti,
0ctet31iocvtluoe9rr{eSascd4fioo3ern0pcreocesingtime-varyingpaterns.
NeTopvhtaomuhaflrrohtoroerleaipadyrmsredrlisn
neitisansomdangoitneixnapicetpvongthntwaen.coisatisooimatrtorMmrecilenkecrhlyysmatnesiivttsmsotoeehauafdcrnraebxytetfvuaosqosmeurrpneurecrmmaoiohpsirsmedeie,rtsttsesoyehcelvc
(soavmtiUt.ewntesunantSTorhbentehntasaydscoevtsooa,eceenrlndbaxleacyadniesnesoerupt
{datbnalitSntnetusawagpoaacdoirolscaasbfloshmsyrpeomtacthcfphrdaeriieaaiaaxsbitssrcitnaieetentolmcciidegrenttr.yxuiecitn.zapxtrhaeecleadtstcEhrtieo.iaoxmirmunnnpnAsegepaetnnoerosthfityinmsertvseahaehsenltreeinoetctrttsrshesvos)
t:hrieatotoateataerrncrutrsaetmrsutdapehper,riorebtmrermaeiadtotsnes-
ihenmctedmneatlaiotirtepnlnemrmoedgpytieroanmmfoucrgtuhcyssaeoteinmuindtstniosrgoeqoseeltrcussssylveeweaatavvssitlhleemoshuirrfncafoaeaehygts-
llrnon-
1sllorotmiyeuo9rfncoi8ecatoaar7ahegte;rdtannnrclieWetlifltetbetoaiwwnmoeursigsnotogppeie.rrenasoskkngtrItddancaeFple,onrossrupndHucorlrsrdcbueeithtlbdbhxebhiiemaeancaermtgtmntitbopaevrlanetaisalvnewckirniat,y,onaeuar&agsdoskkvenccsteRemorocrt
(eluowuleaternm.siteocgmvtuctreeio,krleconheg.CantsmantiTuroeisoitzrnghgufetoahecif1srlhtvepsi9nzia,brsaeteouBe2suutat)
rrort\h.laearthesnpayla|
Hidpaninsnteoievectmpwttdaieauserluauitnvtleura"oeshcsfl,reh,elco,a
\ilvstoatt&leeeiufesvmcrmsrnetKieaasfuepyrnurpoeitternawairisadcatnlowe,tlai-
renmnoadp,redrtinart1meeslo9radae"tsilisnsghp,c2soete;iboinirrcoLoeriwintlnesao
\hiastpsnirmlieseusbg|
dpsciacnaeitasxaiugsesrreprdne&laptaiolvrroaneFtopnrooisraractenaotaruntyeubwletasseereoae"rrndltrs,l;
asapTfboisoemhrslteeuseuIatamnnltamttetpapceirpapntomllirienleonopyotdnporufaarrabsAialsltaelytl;cta,peBpatr
urereexsmev.deesipidpomcouo;tirZainnsaontslgnieeyn.prppavtaiutIartmntoltae.bser.slTpneusamehTcrrrheethieiciictssonIuagpoaislnsaufksirtsistinuli,palotmuttoenshriettneeiirnsmttatvhntieonaeaelttdrtvwteeitisimoisinmnrdepkteFerrdnioiinigseoscsputeipqeercsrduesnaeialdnsxl1nyseg,
(tntndiwot)
zoie.fehstddcFpicrooawheinnrttilttestyueo,hhnroaondinavwnsialsdslttcrhhircrtaeeoaehttlnteeceetuveisbsavnretarnoureestilopinevcusseti,nsfiorftansovahepremsirumserieetniats,wnsitimpbcoiboauurlennkett.
Mozer 2
issovpxFseoaur(inmgel1tautdup)eaeirsu.cdtecftti.auoioolxtnAa:fnu
(rrott,pAt)
ehfrabebetvsuTdhskapttiel.hrcrueetatieoidncostipohncauftoflylootrtorrthwac-
metaateutnfirtolnimtabrmpitmeuiaemomtentmeaotcaobZwosnehpmtoawte InphccnegoteowAesdnnnasoecreohnrsentcfokdihphtgtrstehnit?
oHust-
eifeteanuAeitlcgttnlrhntcywmpesahuouwdirnnnmtieceesseros:tteouiem,imnnrnWqwgapcou
(lthhotrethnyiannhcl.ieteeciosstnemIitqnstvmhruspoeet ssopppTmeqfrrirroueecaidddaeoieiisrnncc,len|
ttisfniieooxstcgnnehti:(niev1aspiG)teycti,oyititxvniimaein(nmgee2c)
octa,wonioxmgshnieTeeu(trr3wneaa)
Mozer 3
x(t-3)
D
...
Figure2:TapedelaylinememorymodelmmTFaooopddreepmllssevdtsahradoyte:fhlmaasvyehemlonoinorrytetfy-
ometrtemebrm,emceoonnretymexnptel
Mozer 4
0 5 10 15 20 25
time
0
0.2
0.4
0.6
0.8
1
relative input strength
(a)
0 5 10 15 20 25
time
0.05
0.1
0.15
0.2
relative input strength
(b)
0 5 10 15 20 25
time
0
0.025
0.05
0.075
0.1
0.125
0.15
relative input strength
(c)
0 5 10 15 20 25
time
0
0.025
0.05
0.075
0.1
0.125
0.15
relative input strength
(d) Figure3:Thekernelfunctionsforc woh=nevroe8lx ,,uift((oictor))
nd=aeolgf Xaayttmh1lecminii(eantpmmueet mm)sxeooq(rriyue,es;n!,c=e
(w6ai)tahandade klae=yrn-l:ei4nl,efaumnndcetm(iodon)r,yac,ig!:a=us1i0
,n(bm)eamnoerxy.pontialtracememory, fEFAoinrxgmupersxoeccponiio3
(fettnam))nes=n=tehmtioai(aow1llrsti10terrtsa ahciodicefe)
tieshtkmcitee=mu;rreswnm!
seeieimsolderf.yuoinnriscytthfiooernmn.eexBdtyuthssiurnebgesttsihetcuettkiionenrgsn.ealdfui
necrteionntkernelfunction,oneobtainsthe tw
(1h9ee8re7ex),p Moinloieeznsetriian(l1t9thr8eaci)ne,taemnrvedamlSot
[royr1n;deto]tea(sF,nHigooutgregs,h3aabrn)pd.lyTHhudibrsoefpromroma
noa(f1tm9a8em )
o.xreUydnhlpiakoseinbtteheeinndsettilumadyeie;lidnreabtymhJeeromrdotrahyne,
fgcsxMutarnirn(eonietatcz)
nepttegier2rorrteenhsfsseo0taorrl;svfue1setnaigiggnaontalnlhsinniodtnptrhhfuaoeiatsrnmimdnneempaomcutisoaitooyyr,rnesayttdiehnwxitesipiatmtloaehsennaetes qttnuit=nseiipang l:ucnl5yetti..s
ocTFTbaohNnihtretoispinmbnoemisetsttsmiheat|
aenioonlcertnsesyhset2,bchmoewa(cnt oiost+smmih1td)
eeodnsrroioesfaatnrtasbehonecieitqtesuensisn,tettrpnraiiiucnnnnetgpgs.euo|
xitfnIpswfbowwitinnlhlhiealeinlbrcytmheaialdelwtlomihgasmetyiot.sreksym,
Eehrivhao.neevraeny5eslwmmiwmniifeeettonmmhhArtmooanntx rrlhaolyiiyieet
(ms:iticon)bopanfon=soouscrrmintomsa1ndatanstianttaroitiyo npfaniier
cn)odoxliponnsiiest(ngdsratitmtttyehi+hooeoovnvwfeminicxeex tegvxiomiep
(ar0rtosvo,,renyir(=et.ax1 ng)i1tseia.std)l;iAe txxrs2acp
(ucwotelntitemx hfno3etrtmiath)aloel;yr.nideewesulxe arii
saygl(httlthni)
enaed.ettwOmtoohnfreeekpmax cotsaiortnycie,navxpntitheurwbeatsece.etxcxTaoppnhmoodennpee uunnitstteeaiiadallaloilwttnlrrctaarfhccoeeeer-
tptwGcTahhaaiwseesatspehotmredeocdtbephfimileamareMlleyoaescmwAnelamin.se
(snimtqeoeae)
nootmacsfirona,ytonndrdasrneotedypoofxittrtpaheirvoosaeennanrieadnadnlifgtlorseyietrasasmblostepaitlsurattratinieoiccopnneanrilnemr
(msgedeeloaenvmvtatVieiorvnrdireoigieeuutsassso.v&iinentRrghPtaoeeargruievmngtarmchelaislpmoyceoedo,fe
\ro1ltydfsi9,emtspthiehzteheei"TnMqphr9uAeue2fat)(een,1rxstcs)epia
qmtoneuonodebedhnenpeoctuleweirasaheTlfldaatohprrnteasoebcmbaecahcyonmkardtereihamnigsecteotondreraeerytratihzaiiloeestl
lott\miiinnrhfRnappeeetemcuusshdseettoeeoamdlsrsnVu
eyeidemtrqrqmiosiuuoeetenenesonxlnmn"ryspaycicnoooherenmdnie;osifesalsePed,nhrnltpsritsotgiihranwrhteoeelcosfcirdetdpeerttreenesahhvplotaceee
(tleydi1hunksd.
9tlfeebiioArnogaurnnerlm,tleehommleliawogfteetwui9hinmmoo2ngrnr)
coowee;trhrasshiyyaooaoiclvnclhihuousheointttgliplitoioodhonirwnnnsotfduoh.pcmedrueoopmemaestnpemrahutsdtoheommifraorbbynmeimunemcertfceaomoomhonrrnomfiyocgrrmrehaehyyrctoenrifomlmooeidnnnsrososogmtdralryunsetbuthlforscoietoauttrhanntmitatn,ghtetadihwentgiveivgheaoaisencnrdferiteruaqeudoraabuaamislslelleitnzteseahhcel.lneieesegtmm.AhaeiIecenxnlrnrnopeotttwtoshssseonserolodemudpffneteaptsttiloisahhtaothnyeelf.
ldwnAoeeiwsntghbasditetecifcyvpooie(ntrftheutb),innit=n!
couotioi8:<>lmoouisnwsia 0,atlrnhiemewstinoniehcltui!edectgyhti
(eonh1rcnaeadmnhne iialgcsaimesh)y,r!evdita
+ehegn1paead rtmsehit tm.iih!
saIeliniaecmscodiioeffriimnrnsttecto< srtinprehyutoe!
e.oniiiudnAe.sqitnleuttgrhiivmvokaaueellg,er[nnht0hte;dle1oef]
kfo.VertFrhrdniiegeiesuslgcrfraaeoemnrt3demtc-
hPtasiimrshdionmeewcnegisspmaieatmoyrdrmyefeupaainrslmecpastereigmoinmantoma,artrtimieihvlsyaee:
sagesaqm uAimesnacwek0iectrahinntetrblh.eeedWcueocixmtephspo!
tunoiteen=adtdi0iane,llcatrthyeremalcigeneanemtkakemlerlrynane
(ekld,le.ertnVheerliercesod&nuvcPoelrsuitntiocoinpaneo,ef1x9tphoenegnatm9ia2ml)
ta.rHakcoeerwnkeeevlrenrwe,lit.tohInctohtmhepeiunlitpmeuix tt
fMTwohirotehazergbrex iocvuue;jrnn(sdti v)aear=ynudpc1od!na,dtweith)
ieox iqcnhus;jaItwio(intlidse1n)o+teax sx ;j(;t!,it1i)
salsonecesarytocomputex ;jforj=0. !
16IcndlyanouierenpmglcsdtEeobihssnaaetcslirxxn osthodrwofaus;fjpemccds1thot0et
(aiitoapntene)ftvtgnyehe
=tadsivha+uexglibcclg(a1yhytthmos+ufvrrtamasneam1rwstaiy)
oseiililmeinutvelhffgdteesooiecm,yorr ntwnoosa.a
trrillmtalslyAh,t
+tjweetmf lih1aarto:rmeeh0gprx, diyaerl.eyaegs;sn0iieidvg.nycentihneeaalxr td rismoa;f
ncoaut..rsemhBtrGiiasgszipveshaedeedncgdbiaefo
yympn,t mthathihaselaseoufnwlatamdrmrargp
iedetlsiyesioo.toln OuT!
stf,hbiaoecedbnotegowunaumreomtseteenetmm,hdrtoaeeh
rsmdyios.,oelmulaTmetaahisoodimernnsy,tatoalcooltnana ndael
cetbpOTahaxrehtneepdemdhionstinetatcrehieitriunmnnorrctertfataeo.idlaironmlmnmweteeedrntmmasapctooosehrrrefeypmideamssiefrctomtatjeruotoommersrf,t.yrtoeedh.rpwFegeyrsohercriserctecihhibnuneetrissdastsitauovianfobercnsteeueh,,ptinssdaeoffaltx oetgcrteatmih;uia
neslwiggsgoioianotrnhnliOytl
hyknpmeiecor=e,nscrsbaeti0lnubatiif
(nlvoFintrieviiegeaweesulcdl.rttieonh.Aroi3ssTtndwyhab)
seietkcnahepaoirnandnnsiessrableeeeldcffeatucutmnteosecexidtltdtyiheovenftneooscnritroeooeinunsbrrusptoalaumftlitsnntuhteisnaoet
mcf&casoyaotrimsmHaemeRlamsposcfauppuhesdt
atnuaftrercoctiitltmhcrdiioicd,omeanun1Nsalsesa9lttmer8ehoaal7poyveln;.red
(ugyUrpSassaenuaeutrfrncosu
sohsirolxkuianacierngsnaoiddselnthrhivrcaenneaooqtaqgtmleunuuirtvimtivrherieaHoeenulynmeonpovspcie,acfoa
nalwitnuenttislhamtidbo.it,ielneinen&cbgoto1eicmT9mtgchaiapen2ensu.n)
ikctoiWho,ennnda1gahvs9lbaolasyytltuu)amugat,nsgiao aeeikndrxsneeteco
(sedrnBfdetotpomhathdoeeetcienngelnkatarthearsmriaislnbnumuolesytpflaehdknwpemaeri&rtptaenehacmeWtsptliotsrch,aroaetyiiclbh.ieeabneadnletpucduar1ater9iut,esssweepqs;hopouTlefeyeracnntenihacoakees-
l ogHinfaetmmehFrmevaomaccsrai(l(opatmtw)rrn)yoe=yid=pmstkojXthoes
arret0ytndei+Pq.ejvalcj
enf =cu;0ittjnnio( cctr.t)irsjie,otTmj
nh,einscoiiftstaathwtpilehhpure wiepcaohditrsrasedct.aeetrnotpi
+obbrfoeetceheaxdeppuprrrooeeslmysfoenisdroinmmagsieambal;uowttrheiaeiegsshubytpaeedtsdeaudstnueoemtnximptolhfeoirgsiesadkmienramdnlteaeeplr.kenenTardtnheieevnlestn,utoomfbtt
(hh1eeer)
dgwMaehomeVzrmererix eat(shmte)aen=qmdjjXoaP
rry0reiqnstjtchx aiept;eewj:v(e1eigc9htotirn)
sg:shcoowe tchiaetnttsh,ethgeamremsualtkinergnmelsemfoorrmycaabnabsiesesxept,remseeadniinngtetrhmatsfoofrtahn7e
asHktoCeorefatbrogcvnioortinefnernlaagsctvt,rooedyeblpvne kursiaenttccrcrgisonetibinneacoetleadcsfflocufuatmnsqhntcjphietgllsiietfooesoyxenur.rcmkftchre-
otrotthmnhfaeeattltrthhwdmeEieistcmqhasueimyamtmshtpieeoeolxrneimypn,c1opaIonuhsentreonolsytdtweihsqa.atlultuyeTrnthnthcoieest0oarreteatsqhseuuea litcrch!
eiosdntei1tmcaeons,emytt.shpttAoeuerptlietan,htteaiouxonuiindtsgtfhcasoomratnhotvsehueaeqnlmuutceseeamnsoetesfolsy
roe,yfniadtsmnieandullaolsyyatt
haMisinnenoqeldtwdmueTheiriothnmnixrcecifi0hssoe(ec r,sotatm)
hafhussie=aettsihtwcliitixenoozar(pninasxn usna0pg)
itsds:nefsteorsouhrtertemaiqmsdtiunehetediirdennnapcgxrnpeer.st,repfoevorxveirt
(oimhso1ueeu)ansislttnyiao.sptenxuiTcot(twhntiso)
eielt,nlqhmisbusaeeietsmtnrciacsaoaennrle,lysenitfddceoheonreinmdcnmtoepieddtuedyimtniinotgnorrtrtapoyIhnreomdsafcomoeneermseesmswmonacrooatritreienoysph..niraneMTvcselehounutddotseea,lbtsateihoninoneaftx dxthhid0e
(eia1tnrir)oeea.nuwdarealix nls0np(ntteeue)dptt,
lantTihntoheednirslsaiptnttaafxuerswna0ar(sdenr( eavss)vmfr)
oei=dtacr=kmtntfoehea(rurxuto+frisuoaue nnlge1)
cohnrtf:eweiatots hnuvsarlic:tgfetsme,iviooantitdhiwoaenhlranfctuolannIsclswitneiiseolanor,cfiatwtylrlh:aainchstfrocaornmmsfapotruimotenes.daFinwirpesuitgt,htothreedTresIuimsmeaomtfortarhyne.sfiGonrpemuntaerteailolelnmybefyn
(2tiass) aThtnrSheieehdfreuceeidosrrcceanuultnldexroran,rr0u
(deeaet nnnstsh)itttetts=soheinnnqee(atfouFuesn
(etrritxrgnalnaaiulcnnan erelndse)aaempf;rot4rr xdreaota1mm)cr
(ar.ae ceorsndh)Ncrs;shyiioitf.ninoettsgcrpeetmtcauatutx ttrhaurec
ataer:hi(nteoii .dtnnt)ehscwcittsaahuntairecrehbco
(herFtithpTiegeecIurStx fruoeimrrea4menbmiesd;doeqxr.uogy0vi.tc,eeSorEurslnricmemohstapimlnaoo,ernnm1ldty9ootrtoa0ihe;eafsMacccitroauilvznyriertebrci,neoestm1i9miimn8nppotl)
unew,tmowrebehlcnuaiutcytreherdare(Ilns3i'onlot)fl inpuTthpiir(.ed ,)
f=orxa(u to+p1re)d;ictivetasksinwhichthetargetoutputp( )isaone-
stepredictionofthe
Mozer 8
input
x(t)
4:isttovpnwthanrapeoleounuceTdchteasaiIdlsntSraidhdnyceergeroenrep
(npucarlrscnaue)
ieodiycrstrAreeeesredrrn,ensistTaantapanngItornSdienoeapdnuelmrctsae,roeeadclrxtlmhlinaoc0n
(apotatitetsrr)
ohiteyrvndeoeaaiwrcntcnccaouodhrnagreniretpttbenteherhneceneetteustuurrese
EIMfcntfhox esonettsih(zetmitrenes)
artegpsimm,atalaiorlsyiakrf,ymeatbhetwyphterehaeenraddsebtjeuuaeatrssresatterpilmnep
ngcrxietneemstdeddoieccfmiatnfntiuoohanrnaedycsdivtnjpiapuopansonurtcsatesomm,isfbeoeeltqemtnheueeorgesricn,viyancetnephnpueaacttrranhealeslemauetvqr
ehaautxeielelerannmdsbceeletretm,eshpfeoxeorlre(remy1csmt)
eessn.amt,takwaotiixtnricityg(ohtbn)
prien.ercopelafTidrmueithcsshieeetteinsotttnohiaannsestp.kitomuIhnotneefmihacstidaohsadprtedyoiatanrcispyoiett.tunayivrtItoaeen9ofl,
sleotFleephxfiaageepdrrcuoTInnneinrn
iilehennateeteeyggnwd4rstemotoibisao
(rsftyeBklimmignonidsatgodateesmrerkecciympneanmaayhsspsmarieacrarsuuoeamamndsdoltleleiefeyeicnmktlsateeaidi&or
(olnnysBran|
ypWsaaFtt,docptiiahtgvahaphiruepabrareratteemceimlnsvbh,eeee2eerm1ustvm9treioesarefr8slsaymau;nc
(n iomedUlriteFetcoynaxrmidnVeatabeniuesrmkeltcisscretotpiarshisnlenaueheil&lsenstpevooahGraPfnweelnoerd,aitnriatinHicerhsictnnutooii&afrpoupotatnet
hrilScmeettnolradmacedash,ttiakeinao&ml.riinnt)
a1oe..gTc9rrtayaEten2thrvu;kieesrT,tMrehiy1hcioi9desnszdecoemeqlfru)
nuot,dedh1uetnee9h:ncl8emiettshlke)
perem,eaertoslraocepncnhraeoiydernsnn|dsgstiiennhaiosnggesf,
rSHataaoeodndncichnjdaecuumtSporssoHttnrttinaideeossv,tnpthpeiwrtcu&
aiannbeimnnoleeWdtdurfeitrmmi(Ehsla11lteeqoil9a9a|
runtt8myyai2e7cittp;ss)
mi,mWeaonaorn1reoocid9gmlfthle8uiiial.oa6tenssrme)
fyfTcocpoostarhrbourmn&ewerarecaeebEZatmarteiiulfrlopmue-
asnastmleiaienmarntrote,shehredaS1ayefsu9wtrRotet8lsihNlrcnthauaahb)
oirtbanliubroslliheaegwlndanacognlasktrsbpipobhplteperhraiaaogropmcnrohcpkrnaeaeadircpsgdneEheuarasgrorltopmviiepf
(lote|uoaaindtvtrgnhwieatoi,eRhnthmnr1riTieoot9cefRnhuhomisegr0Ltaoh)
h;amrmrertdylRieciooeemmeomuqusnbgeunootsihatr
(ndoseyotsemtv.erolitemoneBiFdnnweoPotb&hstrmaoThecaerFaarTkxneitRaan;dpltTbmRlhrskdeRoiuepdntepmLwlcteoearr.we,egeael1aTlaihnen9staadiii8rnnnaog7tnngkge,;
trdeaMahevncissheetonnieionleturmvct.ttrehiiTedooeoannhsburseiynnfyidocgnaerecrdttgmtrheaaaeepoamixntrsihntmeiony,pnagddur-
ietofersa.celtammrsaIetonfiialvltyutsyehit,enietvofgroenx enr-
tiewt;shs!sieo.lto:lhupc0Ttraiine lhoscentere!nemtatarrspatgicinou
mergmag-eodl.efineunAtptnhcstcreihees!
raimntbsiapenaeisucsmnerttwed.oyaritysiohnenssutt,hhagteeghseeoetsxactscptetiudaesrcttbreticeyevandtelchcetmtiesoomorfadprax egonlur;am!
ionlfperlneatupegttmrceeoapsvfneoetnnrbhtatees,l imtfiI
(tnehdssethoeedatdanlThatbfveoiyeaamlecrsbsw,lloidliiasenetsaedetaeros1ra,cdcfraphrepettnitcxhubrhieeevpereitndseedowteT)
dnn.ooevDtetrfnahTnskNlrteuhuseiaNwaeoenecslimihtC,(tdthW|
earaicmanralcawactdoeieesdbhnmss,aeiesi.cgalbl1lilahoanieyntnmtiThpasssematrhpasiaoleoa.ealdn,nocIuvot1ens-
arncd9gaeoltl8euimcfln7woeeam)ebsf)
yha,eataeirdchcmnmrhodteedernsoinamaentrtngveyhedoansuerioffitmroylofFaa
(rrebltIImminRsh,lnesaeTteaitnothtinIioennoedumpnsTtrsuhcyeaoiItomemSlifen,stnnplotedhOeelerqesextnysuttitt
(enTmhWlnpacaiOcorlyualateod,etny.snr|eT,s-.lgsTstOimaThxIwnvS-
iIasdaddi-)
itdre,nivhsylectaoat:loaeinylanruixydnrmcmmiesstmaseteeapdmic)
monloa.hadgonpoisIersrdtnsmyltiaesseosbtosfrh.htoidylaoaerievtsromlyaeeesf
pa1l9rso8opT6bo;heseSeeoTsnmOasptaTounIlddiSniTe-
kddOseySelax&vytaermKniesetaiimevnsetolehyrrayvwe1ini9bt8ehae6innn;eoftotmhwrietoatmrenkdoowbrveehecrpoavuhsiseyeeswdtiych,aensylaelyemhaKoivcreu sierhaenncrteeei&vdgeodvnvaeleinutrtrnlHeaeledsmtnubedmyty.ecanoL,my1ma9puun)
ni.toyvH(efKurznlecitn1if9oenlda),l
McmoozenemtrIeonrtysTELaalmbpleaedne1s:&TadxeZFolaianpyrosbemerr,yo1f9n8e7u;ralnetamrceehxmitpeoocnrteyunrfteiosarlfmortemporalprocesginagma
10 TTOIIS
CW1vtt1HZeho99hoerail8arsn,ui26znbnm;geoSvelrooeml9tuA1Hpmtaoullea.lt;,iscn,h1sik9&nK8ys7loM&e;ninaWKfrtetaahlindnnis-,,M?
JBeGroaoorcrdz1hie9arr8na&,ch1S,9o821d79a8,;F2rasMcoonzi-,??
d19eV2ries&Principe, 19bOsmTMuet neI-ueoiSddnmcdzM-
eeigeyeelroraxnoricyaptvdi(eeio1earsmnnnn9t.lgoga8teenoiinmtcnlrot)
aiiointslahtrheylhytaammomevrtemsthefneohmapeecrettruooraonnrrrydpayedea.toclxaopsctTnienotnedhiidlnnstueiwgpatmtmiuonhotnrtheonk)
Tetsi.dniIvA oi-I
aeTninRtxeapitrMpogbaheonelrneAennacuteeme1ninrmm,adetbBotlieeeaedr-
atlrdlnwecyselomh.ie,lnnraeMeawglnymicneohthtdoehzohareisweysrr1e'ew9spMmMi8rgo
(eAohrAdkdt(,iseqcwcF.l2)toare)
Camamsdmnostpocdnaouoodnnldnndetodielieerss,sns,caiGctcagAcralntoieitbnusrlraieaienbcdslcot,&euoenaaurgbsnSrrttacedoaprosndutuemMtiacdtothspna
(eoiur1ddmnttt9diahnofeOtre2ndio(o-)
el1md,uanl9etnaailtsnilaa2etlydnyasr)
aVtwtsnwhhecereaqkaetirsewunteAoseoaohusn
wadratcxkntapldeeehdpuddetdmtD.Pgiivtem
eurheJmieronieoriritmnocnredhidrgnpoeyattcrrethony'artpasl;aiun
(mtoiidmd1nnstue9siinhnttir8bchieig7anooie,)
llgfnhittfshsitiahdtitehamesaedsesstn.eutnntiTiilnennsaatctgtuowbeoi,nofglroheinprirtonasokswttrurheoeiaegsgarstvgsprveegeaedorfistvon,tbiaerosstemnenhnee,tniftOhnuataegchn-
rceogectgaxnetuapsit ao
mlonolonnnwemouseedutnawipgtnttprumeoitaaurteieleagtnvmnsrmalaebaolIetauu-
rromrgeeytrnasosueilmrsodsfayceom,tnadrhidbalmneiunmmittalnsheetegaessmemstseaaeatqoodtrurcas.iyycoter.,unaeidarcnTfselieteehdthdphibosrbaufuootmatgdrchtumegkhmclt.oetihnoibode tranyoyeil
1aomeidtx9rfoocaimchsdmoBWiae)
untepliehrsnoyalcseitonietla,nendu,cnidrtotdsdaehhminsatveithsnpehcIlerrtieoIstead-
meeshtxdei,ramelobeaabsnnltiykapunsuoy.litirmevmneetmgy,emhmaaeeraemnlenotmcpdhroeroyIorred-
rtyusdwyoageeaienihnlctstathlttysacnahosaacoesmnhteyrTceseelad,cIumad-
asshetdnooixoyorrnpbbneyaaosrebsiinwsdspleeeaiirtntgsli
hhltceeriahsoiastsaenltosmwhufmcToeuehTIelsstiSemIcd-
iahcnedoatixercnnatplyltahanooay
(seanlMsalsemydooncozeefteizsbmnirimeaegtgrloane,crtimm1noyho9neofecm8srmesaiypold)
lodaemi.risrcunyTeeebldmeth
(eosh.MesofetrmTpoIytdzoaheheesmxmeaprsovieooTbn&endrioDydlepimlstSNrm.iooyeoNopusSnhdko,oaaetsumfrhelvopesdeeer,,
schiruzibetiecaran,ldPptrrheolepine!
griteirde,sel&athyMaptoaazrraeermieg1tn9eorrs3e)
adrhebaydsytpnhraeomptoiacsxaeoldlnyoamdteyyt.pereFmooirfneeId-
xdabemlaapsyeledm,oSenmchtomhreyidiihnnupbuwethrsice
(hq19utehn2e;cemScaehsmmitoirdiys-
atK(pMySsraspoeonoezicFctceeoMaeirsarrlst,yebtiedvha1r.eec9sk,
8Tmn61hepo)
9terswoati0podnparedaakgarnsantudttenihtoIRdwanheitonrasrlgvtsykye,eisenl1eakgt9lahsetocahnttsieisvirfdoaogapetrypsieopvtrmenaraportidinpaeayicenmhwdntaasiittsmhoh
(tefieocctisgsodh.snii,ussTtcHeiihandeoeruerdrfoazenu.r)
eies1std9wtauionmnrd;ikenaKtnddeltyyerniiennnasapftmmeiunlidticgcses,ll1ieta
(9mePs8rseea6uant;mrtuSlsrimnoeinmguotapintneosstrletei,qnemaus1kdpe9yno8tcrh1&ae)
e.l. HaTtTwinonhiovtdhaweehseaetstv
rtseiaedviIrnn=iaidmntaladh0arcdi.indacsysearIewteqyecwoodeuufraikrlaaralrstemTcrnteeyIothfxSerepn-
ereoleooxdtuufropirirtanoesstlngechtttnei,laTsneyIttnIliSiahaamd-
dlar0cdvimatheriarineetrfsmgdeocshcceotcuisrtruasyetrseecheedwtceufaiouotrishnrserssasutr,reheeqeTtpeuhornI eeeSfntsi-
negc=nerentotmwp0awerteooiuoimnrorckgnroeearsaaqcyslruoli.cinnishvgnssAaieutltenleeeatcssnthsu.ttkouslsayur,egsirne,hacenFmThIoiIsgtiaSutnr-
trdeedoepeclbro4atetebyshueatemnrhrmtsaeeaomtthsuiaotonhvrntyees,
oaatrhateehfdrromlcgawjafhuutoTtpeismiritvtohtnmeeeineevcndrnisotg,TnhtultgmvsIiortpSeehfaasoa-
een0irrtxsymgwhatiiunranrheeehctmpaamheeadvtorixhreeeteraileaqnysyfmctutott,hautieulnwhitintgrmeaeedithtrteifhsstotmoearhrireeetnpdanmtidotoeaoEirrsn igunaqsssrglscutuaohusaadtfetlthihtqiliecseoeiunittdaeneeitdrncnsnmnsedtec.
2inlcpeenyesBsoagusc,prnesenaeioandnnislwrtgtpyps3rieeoierrsacuctofinuausnFcadsilrelornklrsaitygetns-
srrnistcnaeaputholgir enonngivsaiinrecn,aeantcingaewdtidt,nnphioetldtpareinlhntrkyStteefss-
ioodp.pdmarioaheMcrmawsnactrcihaonedoletziordnntie
(fnloetu1regctnl9pata.ttusrreo3korbmTe)
cs8id.tehppsirds,irhoascue1rorosra9yuiveesllne.tdi2nrataI)
tscbtntekihhhelrsliepevue.coravsasaOrtleopescrdnrtataatiiebtccnbeoaleidyessfl,
e1Hrw0sneiv9egiocmettnwownh0Weige
;omenbvcriWxiteekaotahrenrisa,monitTttentlropsyhIioSnlblewueiit-
trsms0eTeeidrror&paDeegafrrsetNcorStiunheivlhNnarlaieaaetgrdde.tsgaeciteervpqrtIcrxeiueuh,pilkrranyil1fetntoto9esesoerrc8irawmmtfg7vtoura)
aiproora.lnlesfndetc|sohineetfe.onaausttssIeisTkmnidentsIreegab-
istdosochkuTeAetalssnhaIts,tyaefcTcouxtaamItfrpnst-
eteeeoenmhsxmnnoe,ppetrcotnotaerhbsntynveeieaa|
indnesltoteoxitmissnlpavp
covleeenemnidoe,edecrwcobnhmoreTytnidieerIasTaesSilacndIs(oteiSeBnrgxr-
qagn0peutcfniohueitmtgnieleocieevoanomnsa,cmutltuouiDciaprsveclieioeseennmssnfgMs.eoefenruTuoAmttlrrsI.lhiaotS,ehlarTi&lnomrelhoueeseectwgCrmyuhseeairpdoerrThelreddeatiIneiechvSntsdhee--,.
tottouwics,ohorfneinentiigbctghenhierhcneeaaeetacqtcnes|tluus
gitorainiieetmnrnrecveeygtteenswsnfttmaio1orsrenirawtflnkecliolkegtoa
(iwe2tampgulhoyhpnFphsrtr.iouiktotdreotsGpdimiannrarbeintbgannaeodedttiudesinhaem|
ncdtenouiedattgwnidseltrlnteii,acloodeplodhncelmtiybteeeiwipnmenoplchatnueimesyynst)
e2ewastrd.tosfhiehoktAdbiwheresyldiftBieulesbhlanebPaocstdfychTouohfk,logeTodtcrhpite.gwomhrdrIinoaetnaesprrndiwdtasdeiwhtgeiteelnenwaerlpetituohgtt.ionrohwhakfnfFevtoo,s,eutrnlhsudkriesatfes.eothyidwmntteNhegoarnemoe,reeiwwkcttrpiowthe
\ohnvcieourgoeasarnhreinlklmuqftsB,oesuipctdlesPedhoaqenTeneacrucdrtrnTeeet"eneohicoacfiisetnnertiaa.ancRatpogcciTTmnplooahRasprneteoiynLesqhprew,ouirtcdfttiuehtadientirmitnoehcncenhndeees.
1T9h2iWs);sihtithouwcaeavtrieeorf,unlthissieslteircmutipeoonfsoeosrfsfteehreieoduwfsoerirgwehsattsrr,idcotinnoeentscsaonanspthrweeveselolnrtatssthorefecmgurearmdrieoernnitetssntfehrotesmnebsthuwrtoinrtkkhinceganptrhfoorrobmuleg.mhtiismeex
(aHcoecrhbreaitteerd,
bMTalaorryIcceoSahztW-
lahie0troeehpmpcidrtlteeoeiummmertpeoahislsr.iyisintehslsga,iatyutpuesoarheestadsidovibinesnitlamirctuoyamcn.ytjouuhrIrnteoeclsatdoiplofsefonotchriwaseeTliietzuIhmeSndo-
sf0othcwldmoeeenreldlnmtyewnocpeotretiirsve.tsioht,Tfyiimhtneevem.emgrsaeto,ysirugTynaltIott-
itheinsxabgtpaeomcntnlahaeesyenrsrtehcoisaaersllopesfmubfrroeofermaocctuooestrrthrifreereasnarp.turlgeFenhcaueturtrnrwtwrhioenie1tnrgrhk2t,
miM0IEtnna.cesAxtlmkAuhpmdoueltreesohryiendroTmigeuinIlmgSastht-
ihnbhdredateeehlnseeateeraytdms,xoesfoeoTmenntwIxho-
oOpgimsriaeytyrcmgihhtamtmyamhpepaaamnett,tesaTs:hr ,aIaIdnIS-vnod-
epdagernylaneaOeomsytcte,mentiexTotaaxpI,epblSoxlnen-
opd0oeree,nneaxrlatpiittimnnalhaodeleearnaearmstdnshMe.doyerrTAtbxeihoaremeismdtoshToipanedOhpienbipslgsaetrsnioocatdaafoc
ttThfenhdOmaecnoSymOcmi-kveabdamnlierondloiwaeiarnytytlgieaevdcsIasg.l-
eardeirs,eeiseltteayshsyepadsareseensdwcdcilrecaTiltsblisIoeaSednss-
ef1omttrhha9foireentmlTTriuctee.trohhrSnea,meewds
\dtsTpddiehisnraeaeiissncttty.tkiafathrtwpiasheEosrienenesoaftrceu,vcids"aethibadsuptumteorpsIateaeeaU.msaIatbSrAnupfsaosdlldestccieohthuehlilodasislanaueltdwertgeshnhata,oughsgnrtsieaenhcciitogensnohmasdrnbrmtdeepaexeewetcp:deutalhdierutpibsecisryobheeconydoaftfimhudactcethtaueuitteanrriaarvmgedetesaneerteitxcahtraoygprefCeeeitgvsrd,rsuaiaaamttllhdymuhae.aireennpttgtlioTinsiifntchgtkgcetreiawhrsorrnveeuaioasptbbeslweseevfebrriiorsicooieedfoumshsmstsiolgiifyAmpxnhoauerenprrg,oeteru
hdielasasdfe.syttti,eicedv1etxsee9nimcom,htno0oaaaonnnttttoagdhdhseeeiAknsdrrisgpxaabrtittiniyyseel
iiidnhaonnnsfaoiagstpttuphauThormp-
sietdhtnerapoeoefncluptpiettpi1ltrxorrhliaaintean4in,mtnsftseodadihfenrmoaoabmmgyertepmssodactlreatahnoy.ituteofoiastcwnTvdekcahoahwowtluatiunhsiaavlsedse.seesirseoseacItsqfeaeaeum
ttdrmmrherxaenoiepeeayfcndldsteeteeebsemcrdoweneivteesaoeiecsmsnsaroa
frconsroefhxurytrrmyei.obmgddmasTudaaaioeinythmnopuie'iotsnstdspenheldrsdce.vpaiaoddnaattnalanafsytussthasaratoeestmnotfhthatpestniifrelhgmreehoesimean,mntdfwsoreeateniixptdhnqetheeeu.nimaeuntdlnFintimenfecosonryuprervtteaceoeacshlafiea
TacoaqphenfIudasSge adrengtmaassca.ryeppcmo,hlCspeIiiinbeot.umereuneancttsattwteesuiiIsqnles.ruaegateneghFsnwoseeotudntrhhtlmyeiitttcm,mehhhhdaeeee,
td owttorefnare=assyerttdt,,erTii1nasa
nhs:aginfgenem.tdlTieednipeIncatgtntilphysee,uweddsoaataapcfnnthtsaaadoanionndsntnsdihgaeixexyeedttx.hynic5enTooe7muvmbhteirhaenpmaresutlliteiastsnnhteereueoegrtptfiedeiertpntsasehrpo,ydveiuusrisadc|
ettlitpsvuciusautoeeclolnttqihfrdiruoontaocfeasgtomnestinniokhcnsneoseia,nsdnatdtIeaeneariudusdltaysaraneomassddflt
(epoh tnr hmla)ieeertst|
sdet=meieooswnfvat2aoealhn,etrlpeyeune5rsegnpesstteeada:hhxtnirsctetadath,misseo1s7iade
(n0.dmt5 e,aeoprtyrstfeoltoevso)t2phafba8leeteut7chscetume
(h5siv s,awieennssOdleuuygefttcefkeohtTirhn tahe1hvste)
afe1hrlta,oeithdv4imwmseaeedrhter aatieiohygerosneesesf,
wvisahltuihcEehea cmohbpevoamifnoitsunhsutehteieannstpcioutnhdteitanhingned;pfuouIuttmutapreneun,dttii.qooeuuntapinstu
(t itstiimasetcspt+iilsvy irtebippee)
srceaasuressene tmecsdootnnu.onstienocgntiioacnviinastrtihaaebplpreereponareccoshedenisntegtdo
(Bqreuaplalranertsdiet,ny.1ta9Tt8ih6oi)ns,
t1
(bMvrea9ua.ortgiizTnaIe,;inhrnBhWcegaeavailsd1lecea0rttrnoi.dvwo,Titt1y&hod9ivoos8Senf6lrtee;eeataSashdcmorehsnoisttnil,onrea1ptnaih9usnek8btin5yepu,g)
trn.t1eesi9sTterethwnc0oet)aDnstwodae
noisrteorpgirkroeitm.taneeoartdualhinztsipesgeduaelatrotcroafhgcaehstlapitvvveaairectrnyeiaaafnwtmoicvareees,lasenntathorhoernafmiotn0abgc.lsoie
(zuaLrelvnddeedCdtboveuvanhafrr,airuaivKanietncafcmuenelt1leeyia.rn0n,exot&hvpeelSorouratlennlh1daid3et,,
+ttdawTyhnaah1petds)eaeTTTmst.wohhhIuTuaSeeetsc-nIpg0ahSueucm-
mnsctt0elueaeoudraapmsannleflitodoratoarrrtryhIcaoct-
ahnidhhsd1ieiett.oile0maeauhccybttipltd|
piueulndeurcremweeateasnuhrespsttnirucaeeutehnsceddsttidtiiteifecrvseddaotaeisndtowiinisga,noecs.nraprlheeulrAoofcedutwnudihnsngrinyrcrcgemetwtieninitooimthtsFnnhpenes.igetehtcrcuthoiiiwrdcaeueodlalird5encckn.atpniswTuvoueatihtsntstehibiotodasefininrrtmoctehfhfecuairitstntdnlheycegaec,teltidnoTihununeirItedreSoa
(dt-
ial0neoacnacttmllrihauuvceyedhnameetiiutrtisooesno;trcncwyftse.uierohnert
(imeadRFr.idaneiengemTtcnyugahoerleirlueni-net 14hstibrt|htass.oet)t,
cuTlaupvaaaunpahysltridieeetoadTarsrma.TtehetewlTgeIeiidmSotrahveen-
fsiae0rosnssrltvatliimeaovohatsrweeusietirdmsieimdanndnbogtgo.cehor,adptyveasewWreeslceT.o|
osdhrTIenTkeeSanshsns-
htich0esawerytttisheembbiceodreherceenidoomdonntiofcubrodafeam1erraicly5cnoonbahfewesiaiednetrnn.nteueudtecolimrstfirnmiuuenbharsgideeeilndra|
dashdytoti'eiaodefnsncddcdhshelitauiauxndhtnsddaetsieuite.tIdcnsneBdipgbtiuaerssolacInat-
k0didhypt,ipeslemtultrnahashoteyenpim5sddaTmeoghasInraerSicyudmtce-
ihmd0nioonietntbran,efyentawc.rhduvthruonoTIoerrif-
truhedosedgeefbrehlityeanlnhadtyutyieutmmhsmhcTeeeebweIswemS(parR-
etseo0iounogrbmfumihaealthsetses,ilemilmidhdwwnodaeaeirroetatrytnnheer,.
SH5gfvwcroa0euoeinmln rmueteFempocrosaaicnaoellsolo,nlnosymnftewl&oylstpyiIrhnudtmeWsgshtoemaerwntiedolleaealtu.,dilihcalggithemshhRrlteatlprastaesii,hnatarbfhnesirue1nseniet9tngridirt8ngoahiwt6gnnihr)
rnag,oaraisuawntnmisetnggatesethtsoaodrtwpantaouaphietsn.rzaeeeu0ieedndnrtgcToriwthta2,hohtoitneahiesonnitenetnnirndategatniltahietewnwdldhetleoyawavtr2rttohea.kaa0rlet,nsiknhddtworeahueredtcemtnireuoretceaanrirlririlnenireeztaoiinrehtnsrrtdieesgaodlrcsitieonzuribrtneacredtnhioggnherrawiectanndhtdigtteatourhctoansariewesltrnltahiyeisisneieenegtgr,dohsratutoa.hrsmr0nmeecdlciehaTootovbfnhIaslSvoety5lie-
hdnd0rieonagsrvuteamateidngobhre,gdnsemteooais
lmsomsuterretslteyidyests;.
abvAn0vtraac.yutatllmTiuiuWtdInehabhaiseeinleetsixirtgigfoppypoenolusornoefritdretnpthehrhtoidbr,isResdoytemrduie ntemonbavrnsfaenoe,
gtnyllnuvhharseaneaivfnsodmlairtrttrspsmo,toit,aarveaisatrpinvnsniiiaosgnedgwernsiyneasHwtaigsahnuocenetghfbtrdoheetddterh
tmhamahennyeyaeeaea'ndsnntortewufcurd
(hetmonaw1hsirett9btkeraeooeetcr0khruuitin)
ennguotahtgrawofinenltteddd hhacigenoeestGlhndaitsmtdeyvrasmtiesa,ve
rriearanegiodeninreinmfnen,ningtncdoBehtegvatdieweysianptnotoIrgrebi-
arenodns,katcpeeshmaelturweandovtsyenucis,linakergegmseahaat,lateicntnsbinhmhndgidaetcootlgtrDpu
oheytfdosne,oheiijuenintiltsrtertgratfsayc:reatarrioritnntinv.mtigag
(inwc1rgatydh9ahliiirn cepa2lhgaet)onrre.
itteegnhhInxtetnoeetrtvbsaeylti.doB3anetTiecoanhumesseienpttuahftoreearv.msaelGleiedtceaetntriniesogrnaatnslhiedeztaacwtrhicaohosniitacelepcssoteuraurfesso.erpdImrnteaorvenidtocreeoutesspwrlmyeacistnd,eeetsswwctohirmeidbniasetttdioendcysttiofevopladrltierdedaaaitncpiiohnengrv,fsaoeartrsimbasitahaisonounicslediunahstsairnvogedgoubocteehdedneaiuvnssaeauldinsd.iyna.gtitohne
Mozer 14
day of
week
time of
day x(t)
McTpi(n1orhi9onetedzidFae0iiopclrt)
rtiuwoiaroenenpnaisdogscshhoRfetfosaoro.trsfhcetThhnethibehtenleiacsectotttetwmpunr
(ropo1merec9ktoes6sitddt.2uiue)
odlrSsnieeitmddhw,aaialtttasawryteiwopenlrthdooyiebc-cd
ehtdvatwueihnreererepsbeprelehasidcvtaaievcvtretaiaiologbindneesadsetnwittoohesngraueetpgtpeghwreeefesrrortfroeetmodrmlaefbsonesdrcmesLwewintintehschrieoetild
vsniene laaeetlcnrotepdenrtdtehSdtekrioarcizntmnyidoiptaonie1kmask5el.
CItcaflisesuhelroadrtocetssiuhiomeetdrsistdeesoepinriqsfcvvioeuetaimttsduatlhuireresebteeeauitsesctbohyouoopmenofrmrnoeetmittddphdeeteeiiacaawstnntisnittniheuoiarosodnn1iqt neia5utsawtcsadasiairsaaenoseuaslfddmtdneah6lenoiive0nnrrtargermsimoly,aaraamiIbnltbirlouebzyeateenaetdttgdhshoapmoeentrmcheeeToadeermniwxrimclopaaptsreesilqeokrtttuinShimamotsearibroeteofisnndoedewrsereioevnltrCnuhegrftldoooedrrrwmacvhntoioapthartmlhevsueNtpeeidstMeebaiItorteiSTintaueeEi.hnsoss..einesodTHNtbdnhoMttCaoewahtriSeaenmnwEv.oeTaerdiPtrlvmIih,eSazaraal-
ssfun0ltshoieiouzroosvammrnkettlreiainlontyssnoenigsocwraemntitlfnhhetovdaeoaniorsngftletvtttt1hehhhho.id0eeeesf
stEtttTiohohmhxueApetspA1ene
l5ritydnnrfostrmdddtheriimcaieedsnasdeuTttnaWetidcoeomttedofphieimgectraxoeieStonppndendsteireactari,tertliihmnuisieotecxneWistpnrouueyote nrpsirreeiokcmtluhirdseetthaeenieslodnstidtzptbsaet,bsedeeaXuNesctstntiMkirhnpueetgSoxhEZcitlnaorahttamorascgfInp'tet.dgee8rodt5dqtia9teoufsirsnociaotteennemrsdatetvatrtatbsaihhln.iiietnedrilbs6neyeel0gritaaitmesrbeesgiritluni,ttueAhyadtanfetontdepfhrehratneeshtdtunertibcachpemtnerittoeicshtndotetiimcoanmtgpitNoohemnMdteiseytcSlisooEpWmndroeepeddfveaiae.tct9lgitoat6riipo4eoseenneddst:
dagottfsouherrfertcerasthsecntTchsrihowtieishvebenueaec
es cstidrromsuscettmtreeisoeeeausdpdhn.trleeottelotlisdu,effiotrrfAtwi.rooeoRriannTftn,
(h1hec6,beaoe)duxcniIhtt 5t-Teidetgndoreeaudealsnaaonetydyud,t
dsiranta6nsetrut0tiscammothmorcisberdtaiedeenemstrecrup.srtetaA,uteonofralfrselploplhdrwmwriaeadoidirtttvdtciahhhichedtienigzneitoaeegutnrapcahnotsnspueitshairisngnirei,danesibtdpaiptsenesahhtendlwweoirzfwauetaothsenrntrneaimiuot.iissnTnneeTiddiInsTpShgtfe-
aeeoh0rbqsreigeuolmteatsdie.pvaos2asmRdtf.loieecneerlnoTc,gvtait,hsnehllwtelireogtetiIhhtdhr-
ahteedal6cleyttciu9lhnoatrbeehndyreaee
aetrnayxgtttrsecuarc,rearuThpamittniIttothSiioiernoao-rcennng0e-
totcNdtahhhoneMreenetaetdFSlsndhroiqiEmtdaenguitosonisaatnmnqodrresudaei.
wdani,tserhsateHreferloerdkierdbrrromeeumgrbrltiesroyai,roordbternwr,eislolilhiausatfaitobyngcrnrlhhdoedoltnyfshdZgateidi.ill
mly0sili
eonmvrd1edebiireoidnoeevrlcntraminetdctmesoeauertsdnabotnlraeihtnetcphaw.h
(retn1ieeNhe9edavZeonisech2sNmtNu)
aaiMnomMarnngteSpoSstpEtaerEoiynrmsors,i,dnetapwlbldHoepueedrfeurtdfierotnsfdctroonohrmirrbodiimmbntasuansnaaioitgoclnniinnteotceiynedg
w(,tecafbchItaoosuinrasvmtdtpepvipcrpdsaoyaacliilimr
rouefsiudeamserororeaeanafn)
gsc.AclbiooneaiIngtsgcsdlatrcytirotNrltatosaipeoiossngomentshoraisfnp.trogtwbrtAiemnr-
htdtofhoteaattasesldooerttl
svpaericattriuomnsoofnttahsekstefcohrnaiqvuaersieItuyseodf,dtih
eeyrefnotuntdratinhiantgatreeclhatniivqeulyess.imWphleilteetchheniirquexe|
plosrtaotpipoinnsgitnrcaluindinedg
MozerIIa-rddceehlliaatyye,ct01urhheiiddddeennTa(1blm8e4i26n:
5uNtdeaMptaSreEpdoifcio.nt9ritosen8)xte1n5d
(em72i4cno6umtdepapetarteitpdioio1cin.nt0itotsen)sts6e0t
(m3in4utdeaptarepdoici.nt9itosn6)16 IIIT-dddISeeelllaaayyy,
1350hhhiiddiddddeennenIa-rdcehliaTtyea,cbt0ulerhe3id:dNenM.9SE8for198(5
{mi7n3utetdseatptda1rae.90dptaoici.tn9itosn) .9
78braecaprsooesdrsteotdnasiaknsv.TalaIidbealxetpi2oe.nriTmsehetenaytIIIhTne-
yadddIddbSleeesrtlllwoaaaihdiyyyeut,nhTs125etIt0dSrhha-
hhiia0disiindddmmaiddnenuneeegdnnctfhhuIo-
rlddateh,rlgeaberyurutvsoainbligtdaawitneieoigdnhrtseedstue.cltaBsye.|
9eins88sga56epncptoeinaaclrleyerdntethdoewtshaoamrtkemvaeysrystmhwoaesllell
cstvpTTXipoaemhihralrriepfundeeounaerpZs1tixmeniht9orwgaeain8onnant5dsdcghse
{eeeit.dtsnhutc7awigcrmneoagcamseetosshrepptreedeeepsdtrtpueiitotosoasidtnoni2snn6i5agb/
%dtl8ceed5osiotf{rtofpiosrutenhspta.
6eelw,rHtfdaaoreansartpmdidanrraiotnsaenpegwscottensisneiendgfItr,owrtdarbmahanutiicatntfhihutsnerhptgthiahssdneaeanmrmttieanaeesxgntftpriipitnoemhugmreilemactttpoheiimroeneprnteisusoasapdimlnecreaoaiwsomehhdxteaichcd6hfhe/
raol8nttimtrhgta{eeli5eanrviaaendt l7gieid
e.scadeTetrtareihtiooneainnsst.
edItftorhunbaoeercytxmeoasZTopmiwhtnolhtohaepefiertesdnatehrtr.ghsdeisna0eseaHgurodthnc,lnorthidfaldw2siyoit4dneHrae8etvricrunnheetedtgeruasuca,rushdyoneiomitnasisnnttemssosbias|
ofum|
ianntitremidrrinqtrzaoipuheueciupndteaoigverotrianheietrnplagldtewyrnTnaedeat1tdaaas5Ntbirttc
%onlolaMiteoei|eaor3Smar.nfElenfioplonditrhareoabvaaafsaaskrle.ilcv.
9ziAoaddemrRTa4ii tte(hphieot6oeaayrn)nret
aonmttrbtfchesholeaestedetraehicsantmlahomw|
gmiuot.oorenpeuFcgepontodrefuttflarolhreoftoereoaawmfsrc.oimshtneteeHdhgatsdee,ntsaZrircinbyegheag,e'nasrttsinctdh
cdhegaoecaritratatIaeenta-
ns.chdtdtlaweayuIlnHraarsewesyuetsohltne.aecrexorcshctcteiheln9uctdi8sothdo5emae3ncdnI--,
tpmiacarkdawebi.lseeHseZenrhciaeesn,gvthaalenuirdespHwrueadtscichntiionotsnoasnvwatiehlarrebewlceoon6u0dti ticoa3nsaesls|
eocnofrnoadmsssufbmrooptmhtiottnhraseinatiibnmoguetaantthdewthteiismcthesaeotfsp|
roecfdcouircrtrwieohnniccewhaoasf
fMsptauehsrtcsoeeuoudyzMrnmeieccrdatopatkiutioricilnynodkg,nscr.sobesmeutaAcrcrptaaehoiutnvnsahaeeaelncniidtpotd.noterhidnTneaisttthtueioeasrprntetresaetfwldhoshrioepceiimtrrc,sehentdwheiahcethowtipermiootrahenrodpkegripiecosnrttnohieloiaieaktncilyerhlliypdascramameatndoaansni,cdiognmtetio,otptbhntleejehurceucrsyiattstaesectdesrhaksine.aantsdIwhonaaatitlnelapp
brosmeeeascdstastiiika,cbsttiflinyyiitvsgi
netkheganmdrnoto.owhwuAdesniewlrtlcoheocuwrerntntiidtthaaehitetroirilivoauoetnrntlh1gay.a7ee4l,
nwttgppthohrureaeeiarmsnqafnAcocutb7hireca1eppamrrn
%lneetatrgaodihhnvzerfaaceeeaitneprnphctssplheuodcarmen+siso
\rsooaennita rcncoherethelteeiydcwiotnhtncoo4atarlr1easaosnkr%seif
\gensltdesoeiih
it"cnuonietegwntipdpZnsgnresugheaemrtaditscsen;ei,Psca
\g:ttisura.ihueadoepnidnrnos"deiwdscit;cotnnoaH
+ifiv,onnpuosnnidnpetlosmvcrveaehfbccoyoshiielnrsfvattymeasweenconssagoeantsneene'en,csscdxlereoehscitcrcteia,stertuuitir.wnatpshieogntherindveiTt,oftehrconhace
+seeacverxtlacaaliptrorlhielucntoehecrsscolneua+tftetcshht,h
\hsrwainiso stotuouehrmycgdkcahiheehtacalatdasasahnnul
\lbalglrncteeeppoos",aortricrelsftclheudsliciatapisbctunsrllntsrgyeeieieode
cpvn. icev"crasasatelstiTuldloauieeiohnrecssnyesstsIns
\ritapnneehubertasietpitstllwdhpi"iettpioearcyyeerdtatrdksit,rnfsioaotIcdyhirqtupnimieleuosriilnkieeanddtdegdnseiewridcacsegpeietcsrostateleitoeimaoohvrfptbnoeepeebtrlrlroadeefscniticointrmharee5sma.uccp8nashtalU.eiynonpcs
%in7+cqebin1eruyoogf
%eeofofqartftutlcmohwoeha6fesaalad3steaynnee.dlc2stcglave
%eetrcsarheeaomlcseusscfop,ieeononfoswsrrndenrahwoliedccytefcteii
+nrtoir4coe:gne9anpca.s\rlaoenn%anudfoowldpwitcaoccratIshchanfiy
+oaiacnsonhnanniopsogngec.nrseeghee"itdsancThniaascTsehngsetueiehrditscnsieehohgtsswunahttotshveheuhlstioyaennewnsttdgiee,omntstrhtottokheacpecsrceorrhtfeugeuras1fetralrts0dtrtceeye-
atqdpdhhiuor:mgiaideennovdInudoetopticedcfhnrcoct,etoibagrodIrbtta-
rnireaduceiegniteatcwnoiilttnnaeraielndgyygyrs
md1iICmnn9iurgoote.td0hcune;ItialsniRscol|
wlntuylhoumteroehksexfed,lichcioIbl hauahnrascsatinuivsvcgleeitenI,b-
tpdpierimegtreleudeassniyescse)
teaamirntorioecnsehs,xosiptbpeperntleoceasrtdriihunbaiacrtletapeioi|
sonptnorufoaospftrbirrneaaoadlgbtbineinllareiontmaynawotnsdoiretvimrutseswtdearaoiliertibrzcdhkueh,adtinwatioeeiannctxthompounvortoleenihrnsrereeneftaocethrorieamoteluaexpmltottlpeueepnuxrtonstpriaauoaurttnlcnivhsfioeetuitfqsnr,uacceeuottsniuptnoocroenerene,fpsg
(oterBrrhsoe.recseisedahislcvyeshe-, wfe
rlyubiuenminsrhesriicandpltiiodcnthgohdaecIendi-
tiranrsdaieoniglsecbsntloeilaorIsnema-
uyfddrIctfpcieoatfhchalournaaereurdytartienonsbhdrTmiplecsneauI.aepSntrtrmoTehes0csooeehd.ourrqemudylutHpeasspebrto,ttnaeauuwoscdrtdueeetincivphwetoteptahsatirhtoetb,ohehircirfiatlratiivmatiZ'nngsyighnoh.dbiagrtmitee
nAhtepgesrexetroaoxpaepishvtlnnnsroehytiidarrbpinsyceligotHtdenitelcmpheudttaauehtoetscstfetertih/
dhdso,roieonimutmatgdshetrhooyrpacttnlmhhtuoraeigtiet
(trnyethscsee,hucheentiolriastuctierseoternvsacedccpotrsioaaluern,uldnerorgsmsieeninesm,paeengertn)
rptehwvdalsoewyeniefttrndhhdarittegoasuhamthuieethnatetietiostnpbortnahgrhamsottees,hhdpmeeaeeoarlrineodlineopdtdcaehgrebtteoyosaeardfsdiagiiinsoonsciaenglttgiornhiniionngooeesnygosrttr
amvea4tIlhuneoddneoefealnorsgteiheoesf.pZrhIeadlniocgotikaonnfdotiHrmwueta,crhadnindtsootnhr'usespdietocrwitsaisosnst,hotohtwheyeinirbgealdiiemvvaepndtraotghveaettmotehmneatcksoemouvpseeetriotmfiotnyhissweitonurfokpr.mimaptiloiend.therewouldbe
itbMnoeoscbtzMheeawryreaaxyacpitmoleofrridieznidivn.pigdrIieansdgesonenutt'iptnogftchlmaaeiomtsdapexatlocshneafootomrftyphteeoomsftspaiaboxriroclaihntlioitepmesrc.yotcuHiersosewsasilnelivsgeetnrco,ocomistmumsgpegoeaenmsslstysinolugitksheeoedrratipnrhoeaatsthssioeibtnilaiiestblidlenes.e
cirensststaharetitlysepmtah1pc8eet
AMfafirnorenorsycmepaeaktanxrhtronctahtehnineoncykuwsmJwsilaaoaotmsnrluoessesf.uAdsorprnSJegpvdi.AmoeirMernemwtadHceesrDduereWotabnpcnsyehrtnioifgesNnovelsrilSndoFFdehnodi,asPuRnvnradeedabrsdayiuNdtfnoieehodrinenldatl,GpniaNaftelunerlfYdasehlcoe,DoedunmJbnEfu ageCmrclgdIkeenenxnvfatotestersSrtocoaninhgrlalgmalaatsrinontdearishezgeuaaieanwbrsrgleciaeorhrtr,fdhgeadtrIhnrRaSaednaIft
{tnwF9t1ouo0a2f-
r5SFkt8hhe4.eaeWnncgd,ohgraTskrpusastguhnegnotreg.ps9,t0Tiaa
{ohnn2nidd1ss
BBRBeaaneclhgafBnsrireaoeadec,urch,hhreaYuDa,vnsl..iJeon.ctHreDt
(aets1lews(9aA1o8Mn9rmkd8)os6h.rB)
ieaL,.rrneasRCdatinr.osnrpSit&necicegiaceChltnoacckerorndsne,oipnnw9reelcest6Rdei7ong
{nte1
(ss2t9Ia0ann.dDe)..pUaSSr.nappTleluoeabulklrpeiesrrthozeickndeydsmes
(ipEnaegdsnt:.de),rSe'nAtsrtdtuvhcsaeptnsueicreseec,shUainnnrdeivncfeoeurgunsnrictaitytliioononnef.tMwwToiahtrshke-
BBeondgeirTivinnneoiohscff,ooeuaaYdrrurpmmr.spleeeaanenFattati,irrroonanUnnsienc.tppogwrr&noooicc,IrWneekPsss.assRiiinnb&PggePrlS,ssoiyycLAmsseitte.paeed
(prmmi1dmn9ss,gaPsI3nI.)on.(fp,pTptJ9phhe3e1M2)5I1T.E8{oTE
{mdhE6ype1,o5I)
p&n2rtoSeDSabarall.nngenaoSmMtrMiiotTaoahntfotmeaueloelor:,aeCrACtCnozAdiknAnjyfug:eMsr
(MtleEoionnondrcgrggseg.-at)
atnoi,enmnrAKmKedNaavdudeauefuenflmparmcayeaealnsnsndNnbinen.ye.ntcwsniueoepusrekriarsn-.l
BCderuirdVtlipnCriemsire,eseeuu,snJd,rmt.iPaecB.l
(rt1mi.ivf9nKoeu&frrto0neurE)
iPema.dnulreaeTririnrtanr,igclaofyiJoinpnn.rMeemipn,t&rwagaJontoc.siaBreotCgksnrosseacimnehn
((sdTa1egtesn9eistmmtcyi.hcusan)ttem.eiihcomoalAn,dlseMotR2lhfere
(ppepoacorporyr9.agtm2nfo1i)etr.tiBo{nenrAoesuud.a7rladl)
agIpelnotrSirn,vDiaeteCnth.wOcmSMoo:snrakTUtatrseosonouwlin,vroeieeCttftrhwAzsHikott:yVyirMmkA
(soeoECfcrddgaC.pean)
olrn,aollyoeAcKrsaeda.sadvdsuaIetofnnsom,cRumJaesons. aiinnnPxi.ngt-
sLyipstpemmasn3n,(pJp.M16o2{dy8&)DSanSMTaotueore,tCzkAy:(MEodrsg.)
a,nAKdavuafnmceasnin.neuralinformationprocesing
EEdMellommVzaaeprnnrire,osJc,Je.BsLs.Lin&(g1&9PNr0Zein)
ui.cpriFaspeliernN,,dJeiDnt.wg.Co(r1tk(9s1u8,9c5t)2.).e6LTine
{ha5ter7inmgi.naegmCmthoaegnmhiotididvdeeel|
nScAisetnrnuceecw,tu1nr4eeuor7af9ls
{np21tecm.hodeJlofuorrntaelmopfotr1ha9el FGFrienamnscAgtoaoae
ncntno,,iitou,SWnsm.Pt..iBe4ctaHiGhel1eonoS2rderg0onis,ec
{sriMtetUo3,t.cynFkp&o.,ufEb&SA.loimsZ&dhieaemDr,dimGcomaue.,rra
(smn1a3u9ta,sn1cR2nr6),.ip(H5tL1{.9oGc2a2)l(.f.1eN9eedubr)
aa.clIknmemptwurolotvriilknasygaemrnedoddtnheleetsbweiloaersck/
tsivo.anrNiabenyucrneaoldnCilceoommnvmpeuar--.
JHHoeorrcdzhaMNR,rnAeeeu,ivu.teMierVnearwc.lhIMJCAe.no(,(1m
(14919p89u7t)a).)..AiUo5Gtn{ntl1rtoa4i4btclate81lod.
{ra5Dnd8ayi.plnylaosimmsiaocfsTpahanerdsailsple.alrIaannlsltaeilltoisugmteneifntuwearocrIoknnsfonwremictthaiotrniekit,satTrsdeeceqhdunfeiesnectdhiabelaUmckna.icvPheihrnsyeist.
iacIeantl
KKul ehinnPNYHJf,eoraillRorLtldcski.,oed:enavD&dSaaleip.lnnvrA
(gaiNH1nsnc9Jgeao8:eHmdf6reEe-m)
tmVmhr.leeeybmnSraEloeeaufqin&gmgu,She.cJtKnhi.etLniAaSclnce
(hnss1,utual8att3leen)C.g9o(e4SnEn6efedlefr{sr-aoe)
tnr,igoc7Maen3n.ooibzdfyientlhmsgeoomCfdaoeNpglsnenuiaetrniuavdrleaNalSdecnatieweptntwoicrvoekerskS
so(l.pctiepePrtsry.o2c(I1epn3ep{dE.in85Dg03s)1o.{mofNa4tne6hwy)
e,LLLaienpCceoLItndunlieAnmenus,D,-e,rUWYaAaRlS.n..idnP8KT&f7goao,-
ernu2F&nmt6raeeearrSrtbat,zki)lekorIirz.zyn,aLy(tR&ppoEirsoe.odkSnA
(c,o1e)llJ9saIlas.n8Ami7(ndRo1)Sgv.s9.a,sPNnANy0cos)MeLtn.
(esil1:Smpii9nynLpsenmoan3esr)aer.
(AgunspyrnSilpaga,eonlmcJfaio9oncln1Msflpd8uoNr
{rsoootmoacre2dtedari4syieton)
s,irnoig&nanpSlgmraDpoLunurp.asoletMSbicinreoptagsrTlisteeanoeistnboueoog,uarrfecryCsatk.eyAzlrskprtn:oyereMromt
(pwEsosauordg2rgrsfaak.a(t)snpci,oep(AKnsR.:daen6vuLp5eafeot0mnawr
{ctraoennrsNikn7nios).ng.. SanMateoCA:MorganKaufman
MMMocoCzzeer5mlrrea8,lot{liadMo1nen2lds,)CiI.Jnn.Ct(JLah1me9L8&bm.rMi)
iEcd.rclgomCeAs,atlerMnfluol,acAcJtnuu.:dsrLMee&dIo
(Tb1fD9acP8corEk6gen-)sp.isRtrIiounoptmnae.regalVahctoatiloiruvtnme
(apeElrgdIoIosc:.re)
iPs,tshsPeymsacrhianfoolllsroepglteidecemiacshltpraopinbreduartlcbeepidpoatlptoiortgoenicrc:enasTlsrmhienecogodT:geRnElsiAxt
(piCpol2opnE0-.. MMoozzee&CsSPrrya,,osRnLmMMteiMppm..PlpCCeasmxtL3e
(aiSo1p&n(y,9ppnsCSmpt,2eoAJa)mu.7.:nks8MMTu,(9Eph3o
{o,edorgTsdin.a64y).dn9,(u{&A1Kc3S9dt8aaDvi1uona.nf)
nmMSco.CaeafTsntOmoneinNouu.,rlCnteCietEsAzucRkaraTyleMl:
(itEAonerfmdogcsrapo.m)
nno,rnaKAaetlidacostvuntiaformnunpcrciaseotntscunerci.sneos.minnIpenguoJsrsyaesrlEtioe.nmfMfoesorruIomVddaiytt
(,iepoSptn.uJpn2re7Hos5c.a{enIsnss8oi2Rnn)g,. MPPelyaaeurrRICl
(tsmmT,,eoeuDCppmctoe..htprrenCuit1arit,c9la,aBtCLlNi0o.oor)
oneA.lnwlpedLlgooae(er,ann1t2r:o9Cn6f8NSi3MSn.{e)cgu.Ui&rwL-
an9CielHctahSeSir,nydn8Ttes6iotnle-aneg1cym,h2esnGsdt)
oaE.rltoeEnePigngiystifp,n(toa1saerbc9ceneeur8dim6rntgM)
rge.hane,GjEtdePtcrixAhcotpiroue:norpreCuiie,.gmasDhreinenanepttgtraseeirencot-
utmnMiroerlenenelna-ltodrtnornnifivUneEeugnnlreiabvbcyleutrr
nbisceeiatatrcywlik,noEDgprnkr
(egoTspip.eanacreNghteamenrtuiiinecronagantl,l RRionbgitPoK
(,niTfsorMaoeoCnucnc.fohe,moBemfdRAapisnen.
(uepn1gntJ9osesPrro,oturSf&y)bCc.-tlimiUheFsIennhEoaccetlEDelrrosesir/
ig.mdFhheet-,ihIneNrtFaIaFnrlEct(deh1Neri9evnG8sea.7/lto)
Tipo.IRnnmaTe1Llnh.WteBoCouifrrtanikcmlsbiothbamyourppimddlreg
(ixpe&v:pebnCGeha3.dam4yCvnbio{oarlrmildsini7gtcs)eh
(erUEorSrnudaoigsnvrh.e)
Mr,pasrMuioattptyaoe,acmogDh,aaietnCtipieocAanrL:ctoenMmaneresotntnorritwgunarocgnk-
f: RRuosmebpE3ner6ylbnho2lgcaae)iert.rnsttreCs,oeirFanrDimg.pn:
(rgbE1oEr9pixd,6apg2gHle)
oa,.irtnaMiPtotoirnAoninn:,csMIGinpiIn.lTeDEsth.Po,eErfe&mnseiR/
cWuruBroomirlsdlatieyrdalnuhmfoacasrtmru,dtirRcBe&so.oofJJNk.cseo
(Lwg1n9YiM8to6iorc)kCn.:leLSVlepaoaanlrurdntmain(neEg.Id:isnF.t)
oe,runPnadalaratrileolpenlrseds(iepsntptr.aibt3ui1ot8ned{s
RumHCelhihlaasurdtva,ilneD&NEDJ.:(EEinrlbpRarueumsmse)l.haCrotn
(nEedctsi.o),nBisatcpkrporcoepsasginatgioann:dTlehaeronriyn,garacshsitteacttiustriecsa,lainndferaepnpcliec.atIinonYs.
SSMccohhzmmerSriie.ddcJhhuuurbbHeeeanrrnt,,scJJoo..nn((t11&in99uR22a))
l..PyALrLueai nprxnpneimnidngagsnniuze(entEwasdmtosorb.rk)
ias,gg.AueNoduOvesau(nrnrace3led)
sCuticoinmemdenpesuceutoqramautileponilnnec,xfeo4itrdyme2salcet3raii
{orpnnt4iinop8gnr.oscaelgsIosnirniJtgh.smEysftMoermofsoudIl2lVyy1,
SSScomhmompli(tenipondiplnschinkoupsyn2brk,n9eeyPerp,,c.{aHt(Jri1.ao.
9t8nPi&io0srnt)eKS.lniaanTenngtetwenMersoroa,rDrktIes.po.
(r,&1oAC9drM8uAt6ico :)tz.cMveiTraao,relrMimgIanab.ptnlCoeerlKblai
(iagl1neua9dnfsimscn3oeg)a,cnia4aCnn6t.odion1tnt5hi9nien
{ur2oeapus6yrs.emhsiemsntetoatrrtyiicocnonmeoufprsrayelmsnsbieootnwli.coMrsktarsnu.ucPtsuhcryriesps--
TStaonrkniIpP,cnerraDtsoolttcc.aiReet,WsueeWsdtviieni,n.ego&gwSfs,LPHIoHnefhotoypttNhges
eiergecsu,lsNdrTa5,a.l7tJiI.&on2nJfHaolr(um1Ab{9eac8rat7mido)
e4.namnNP,yeBruoo.frcaAeSlscsci(ioen1nmg9c8peSusy),ts.a8tAet4imodn1sy
(nb9pya6pm{c.oic7na05cle0a.n{ptrpar9to)
ian.cgNhietnwofotrYemmoarpktoi:ornaAlmipnaettritimcearenn.
UWWnaaninbisotR,keipnEmrlee,is.seSeeAhc(-ianhd1g.rne9acrHlnhaae3l,acyL)
PonK.nagar.ebFnozuscaiPitnrewiasi,otalsneH,innTiueogmtps.wi
pn3Hoeu9grllidksnaes,6ton(Jrn8Tee.
{u,seJp7rcGah1o.l3nn&nisSceeahTtnliwkaeraoneunrpkrko,ao,lrwDtKni.Tte.hWtRw&t-
oi1mrL(k0aesn-dfgo6e,rl))aK.ay.JueCa(dt1oop9ncraeo8nngn7e:r)
cneA.teseTcPsdtiRhv-
iodoeniIngtnseii.tmtmeIreseEppsrEreeeeaErctkioienegTsrgnr-
piadTtrneieeopsldneaeipcncuhttdisiooeoinnnnnytgs. WWaeitgrTi
(teospintohupdnisns,,ies5RvAtt1wo..a8loLup{Srmpk,r3s&eoH0)
SIuc.nhbhHa.ePrsiIlrmtlnorsicdta,eenarLel,nde.Bia(nt1N.ig9osAJ8n:o7,Ef)
l&.rtJhlLboeReuaaurNurnmmnianie.lntlhhgofaAarNctno,enuuDusrat.aillcECSfeoy
(ans1ttf9ueemrre0essn),.fc1rePoomrfe9dst3pih
{ceet2ei0Cnchgo.gdtnahitetaivfuuestSiuncrgeie:cnoAcnencSeocontcniioeencty--
WeigRrfeoanertdaeecd,saiAwnstgi.it,nShgMc,:oAHPnurnoAbececdertedmidoisinanoinnsg,ts-
WBnoe.fetAstwlheoe,yr&wkPsou.RrbkIunslmihsMohepilnhCoganraCtsn,dooDamng.plliiEan&neay
(S.r19mEo2ud)b.ealPninkrge(daEincdtdsi.nf)og,rNescuoannssltipinnoegtas
(rpampno.dd3ee9xli5cn{hg4aan1ng)de.
MWWoiidlzlireHnaoremwauls,lr,aBlR.n.e&Jtw,So&trekaZsr.inpNss,eerSu,.rDaDl.C
((1o19m988p5u)).t.aAtAiodlneaa,prt1nivine2g7s0iag
{lnga8olri.ptrhomcesfosirncgo.nEtinngulaelwlyordunCnliin
gs,fuNlJy:rPerceunrtriec2net- Zhanvgo,luXm.e&Hutchinson,J.
(193).Practicalisuesinnonlineartimeseriesprediction.This:
Mozer 2
issovpxFseoaur(inmgel1tautdup)eaeirsu.cdtecftti.auoioolxtnAa:fnu
(rrott,pAt)
ehfrabebetvsuTdhskapttiel.hrcrueetatieoidncostipohncauftoflylootrtorrthwac-
metaateutnfirtolnimtabrmpitmeuiaemomtentmeao
Tegiri Nenashi
> What does the statement `P=NP' mean? A good way to understand it is to
> look at an illustrative example. Suppose I secretly choose two prime
> numbers p and q, tell you their product n=pq and ask you to tell me
> what p and q are. In principle you can work this out, since by the
> fundamental theorem of arithmetic p and q are uniquely determined.
> However, in practice it is not easy to come up with a systematic way
> of finding them other than to look at all primes up to n1/2 and see
> whether they are factors of n. If n has 500 digits, this takes much
> too long to be feasible on even the fastest computers, and this
> difficulty is the basis of much of modern cryptography. Actually, more
> efficient methods have been discovered than straightforward trial and
> error, but, even after decades of intensive research, it is still out
> of the question to factorize a 500-digit number. At the end of the
> last century there was a great deal of excitement when Peter Shor
> discovered that quantum computers could factorize large numbers far
> more efficiently, but, despite several well-publicized announcements
> to the contrary, nobody has managed to build such a computer.
I have an issue with the number encoding schema. Somewhere in the
introduction section Gary-Johnston textbook describes how numbers are
encoded in the computer and asserts that exponential notation
(regardless of base) is the most natural way to go. Objection, your
honor! There is no genuine mathematical reason why to exclude unary
number system.
Factorization problem is not hard in unary system. Any other NP-
complete problem that doesn't depend on number encoding? Let's try the
subset sum problem. On the first sight, the subset property looks hard
to check by the virtue of the fact that we have to analyze the
powerset which size is exponential (in any number encoding schema).
Let's look into the problem little closer. Consider the following
naive algorithm where we keep track of all the sums, and when adding a
number to the list we just go through the list and add the number to
each element. The list would double at each step,- you may say. Not
really. In unary number system there is just not enough room: one has
to have big numbers in order to accommodate all possibilities. So the
subset sum problem appears to be of cubic complexity in unary number
system.
So my question is: are there any genuinely "hard" problems that don't
depend on (rather arbitrary) choice of number system?
cplxphil
I'm fairly certain that any NP-complete problem can be solved in
polynomial time if you encode in unary.
Unfortunately, the P vs. NP problem requires that we encode in an
alphabet with at least two elements; this is simply the definition of
the problem. See the first page of http://claymath.org/millennium/P_vs_NP/pvsnp.pdf
if you do not believe me.
Also, I'm curious...is Future_News Musatov? A Google search revealed
that this text is from another website: http://www.dpmms.cam.ac.uk/~wtg10/future.news2.html
-Phil
Tegiri Nenashi
> if you do not believe me.
Right. I see that for SAT we have the same decision problem if
variables are encoded in alphabet of one ore more than one symbol.
> Also, I'm curious...is Future_News Musatov? A Google search revealed
> that this text is from another website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2.html
Who cares? (Although a certain full of garbage reply in this thread
indicates that probably he is)
cplxphil
I'm not sure if you're disagreeing. If you are, my response is that
you could argue that it preserves the same structure of the decision
problem, but expressed as a formal language, it's technically
different. It has to be proven that languages are basically
equivalent (in terms of decidability, time complexity, and space
complexity) and independent of encoding scheme, and this proof only
applies to encoding schemes that use at least two symbols in the
alphabet.
I guess something I should have mentioned earlier is that Cook's
theorem would not be true if you use a unary alphabet, meaning that
SAT would not be NP-complete in that case. If you think you can prove
Cook's theorem for a unary alphabet, please share this proof.
> > Also, I'm curious...is Future_News Musatov? A Google search revealed
> > that this text is from another website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2.html
>
> Who cares? (Although a certain full of garbage reply in this thread
> indicates that probably he is)
I suppose it is just interesting to note that Musatov seems to be
changing strategies in an attempt to draw more attention to his posts.
Gordon Stangler
> On Oct 21, 3:44 pm, cplxphil <cplxp...@gmail.com> wrote:
>
>
> > Also, I'm curious...is Future_News Musatov? A Google search revealed
> > that this text is from another website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2.html
>
> Who cares? (Although a certain full of garbage reply in this thread
> indicates that probably he is)
What is so wrong about that? Taking the work of others without
attribution is stealing, like it or not. And some people, myself
included, are deeply disturbed by stealing.
Future_News
The closest person to me calls me 'Martian'... :)
Keeping in the 'spirit' of things it has to be interesting and topical
or it's out the window, so here goes: (*da_bing*) ROUND TWO:
WHAT IS IT LIKE TO BE A HUMAN (INSTEAD OF A BAT)?
My purpose in this paper is to discuss and defend an objection to
physicalist or materialist accounts of the mind—one that I believe to
be essentially conclusive.[1] The argument in question is not new. A
version of it seems to be lurking, along with much else, in Thomas
Nagel's famous paper "What Is It Like to Be a Bat?"[2]; and a somewhat
more explicit version is to be found in a well-known paper by Frank
Jackson.[3] Despite the efforts of Nagel and Jackson (and some
others), however, I believe that the most compelling version of the
argument has not emerged clearly, with the result that responses that
in fact fail to speak to its central point are widely taken to be
adequate. Thus one purpose of the present paper is to offer what I
regard as a more perspicuous restatement of the Nagel-Jackson
argument, one which shows clearly why the responses in question do not
work. A second purpose is to suggest that the application of the
argument is in fact very much wider than the case of phenomenal
properties or qualia upon which both Nagel and Jackson focus, that it
in fact applies just as well to the content of intentional mental
states like thoughts and indeed to the general phenomenon of
consciousness itself.
i
I begin with a brief and selective recapitulation of Nagel's and
Jackson's presentations of the argument and of some of the critical
responses they evoked, focusing on those raised by Paul Churchland.
Though, as we will see, there are several other balls in the air, the
strand of Nagel's argument upon which I wish to focus goes at least
approximately as follows: It is reasonable to assume that bats have
conscious experience of some kind, that as Nagel puts it "there is
something it is like to be a bat" [423]. But such experience is
surely enormously different from our own in many ways, due to the very
different "range of activity and sensory apparatus" [423] possessed by
bats, in particular their well-known capacity of perceiving the world
and navigating through it via a kind of sonar resulting from the
reflection of their own high-pitched cries. Nagel's question is
whether we could ever come to know "what it is like to be a bat," and
in particular whether we could do this on the basis of a thoroughgoing
knowledge of the physical or material facts pertaining to bat
physiology. His claim is that we could not, and the suggested
conclusion, which he himself never quite draws, is that physicalism is
false.
As will emerge, I believe that the foregoing argument is essentially
sound. I also believe that it is present in Nagel. But it is very
hard to be sure of the latter claim, because so many other ideas and
suggestions are present in the paper as well, ideas and suggestions
that seem in some cases to be incompatible with the foregoing argument
and in other cases to point in at least rather different directions.
There is, first, the idea of a "point of view," with the suggestion
that certain kinds of facts may be knowable only from a certain point
of view and the accompanying distinction, suggestive but also quite
elusive, between various "subjective" points of view and the
"objective" point of view characteristic of physical science.
Secondly, there is the concern with conceptual limitations, and the
suggestion that the main problem with regard to bats is that we may
not have and may not be able to acquire the right concepts to capture
bat experiences. Third, there is the suggestion that the right
conclusion is not so much that physicalism is false as that we do not
understand how it could be true—which might still be compatible, Nagel
suggests, with having good or even compelling reasons to think that it
is true. And, fourth, even the formulation that I have echoed in my
title in terms of "what it is like to be a bat" is at least
potentially misleading, in that it (along with the employment of the
objective/subjective dichotomy) might suggest that the knowledge that
we are lacking with respect to bats is not so much knowledge of facts
as knowledge of what it would "feel like from the inside" to be a bat—
thereby inviting the reasonably plausible response that this is not a
sort of knowledge that physicalism could be expected to provide even
if it were true.[4]
I do not mean to suggest that some or all of these ideas may not be
valuable on their own. In particular, the idea of subjective and
objective points of view may well yield a much deeper insight into the
mysterious nature of consciousness than could ever be derived from the
argument that I mean to focus on here. My point is merely that these
elements are quite inessential to the argument that is my present
concern, an argument that I believe to be more immediately and
unproblematically compelling as an objection to physicalism or
materialism, even if perhaps ultimately less insightful in other
ways. By diverting attention, those other elements tend to prevent
that argument from emerging clearly and also to invite irrelevant
responses.
Jackson's version of the argument focuses more clearly on the central
point. In the most compelling version, it imagines a brilliant
neurophysiologist, Mary, who lives her entire life, acquires her
education, and does all of her scientific work in a black-and-white
environment, using black-and-white books and black-and-white
television for all of her learning and research. In this way, we may
suppose, she comes to have a complete knowledge of all the physical
facts in neurophysiology and related fields, together with their
deductive consequences, insofar as these are relevant—thus arriving at
as complete an understanding of human functioning as those sciences
can provide. In particular, Mary knows the functional roles of all of
the various neurophysiological states, including those pertaining to
sense perception, insofar as these are reflected in their causal
relations to sensory inputs, behavioral outputs, and other such
states. But despite all of this knowledge, Jackson suggests, Mary
does not know all that there is to know about human mental states: for
when she is released from her black-and-white environment and allowed
to view the world normally, she will, by viewing objects like ripe
tomatoes, "learn what it is like to see something red,"[5] and
analogous things about other colors. "But then," comments Jackson,
"it is inescapable that her previous knowledge was incomplete. But
she had all the physical information. Ergo there is more to have than
that, and Physicalism is false."[6]
While this version of the argument is certainly less burdened with
other distractions than Nagel's and is also once again, I believe,
essentially sound, there are still problems. These may be examined by
considering two objections to the Jackson version offered by
Churchland.[7]
Churchland's first objection is that while Mary undoubtedly learns
something new when she is released from her black-and-white
environment, what she acquires is not knowledge in the same sense of
that term in which it is a consequence of the truth of physicalism
that she already knows all there is to know. The sense of "knowledge"
in which physicalism guarantees that Mary's knowledge is complete is
"a matter of having mastered a set of sentences or propositions,"
while the sort that Mary acquires is:
a matter of having a representation of redness in some prelinguistic
or sublinguistic medium of representation for sensory variables,
or . . . a matter of being able to make certain sensory
discriminations, or something along these lines. [23]
Churchland's point may perhaps be put somewhat more clearly by saying
that it is not the case, according to him, that what Mary is initially
lacking and then later comes to acquire is a knowledge of certain
facts or truths about human mental states, but that knowledge of facts
or truths is all that the physical account could be expected to
supply, even if physicalism were correct. I believe that Churchland's
claim that Mary does not come to know any new facts or truths is
mistaken, but this point is difficult to establish clearly within the
context of Jackson's formulation of the argument: if she learns new
facts or truths, what exactly are they? Thus Jackson, in his
response, is reduced to arguing in a very indirect fashion for the
existence of such facts (by appealing to the genuineness of the
problem of other minds).[8]
Churchland's second objection turns on the intriguing suggestion that
Mary, once she has learned to employ the concepts of a completed
neuroscience in introspection, might be able to imaginatively
extrapolate from her introspective awareness of her black-and-white
experiences to the experiences she would have if she were in the
neurophysiological states corresponding to color experience and thus
might come to know "what it is like to see something red." Jackson's
response[9] is that if physicalism were true, Mary should know what
the experience is like, rather than merely having to imagine it. But
I do not see why Churchland, if his point were otherwise sound, could
not claim that Mary might indeed come to know in this way what the
experience is like, albeit via a kind of imaginative inference rather
than direct experience. Again, I believe that Churchland is mistaken
here: both about what Mary would be able to do and, more importantly,
about the relevance of this issue to the central point of the
argument. But the way in which Jackson has formulated the argument
makes it hard to clearly establish either of these things.
ii
What is needed, in my judgment, is a version of the argument that (i)
makes it clear that there are facts or truths about human mental
states that someone in Mary's position does not and cannot know on the
basis of purely physical and neurophysiological knowledge, however
complete that may be, and (ii) avoids relatively intractable issues
about what Mary might be able to imagine or imaginatively infer on the
basis of her own experience. And the way to do this, I suggest, is in
effect to invert Nagel's original example, in a way that he himself
suggests in passing but does not develop [425]: instead of imagining
ourselves trying to know or comprehend the experiences of an alien
form of life, we need instead to imagine an alien form of life trying
to know or comprehend our experiences.
Suppose then that a brilliant Martian scientist comes to earth to
investigate, with our full cooperation, the nature and makeup of human
beings. Being a Martian, he has, we may suppose, a quite different
sensory apparatus from ours, but one which is still quite adequate,
given his complete mastery of the standard sorts of inductive and
explanatory reasoning, to arrive at a complete knowledge of any purely
physical phenomenon. Thus, in time, the Martian arrives at an ideally
complete knowledge of the physical and neurophysiological facts
concerning human beings, including those pertaining to causally
defined functional roles. Does he thereby come to know all of the
facts about human mental states such as experiences of color?
Suppose that I am one of the subjects studied by the Martian. On a
particular occasion, I look at a newly mowed, well-watered, and
healthy lawn and thereby have an experience of a certain specific
phenomenal or sensuous property, one which is somewhere toward the
middle of the range of such properties that I am accustomed to call
"green." On another occasion, I look at a newly painted fire engine
and thereby have an experience of a second specific phenomenal or
sensuous property, one which is somewhere toward the middle of the
range of properties that I am accustomed to call "red." It is, I
submit, simply a fact about me in the most straightforward possible
sense that on the first occasion I experience the first property and
that on the second occasion I experience the second property. The
Martian is present on both occasions and is carefully monitoring my
physical and neurophysiological states with an elaborate set of
instruments that he has devised for this purpose. He thereby comes to
know everything about those states, including their causal relations
to other states, to as fine a level of detail as could possibly be
relevant.[10] Does he thereby know that I am experiencing the first
property on the first occasion and the second property on the second
occasion?
I have stipulated that the Martian does not possess senses like ours.
In particular, he does not possess eyes and a faculty of vision like
ours. Thus one thing that he cannot do is determine what property I
am experiencing by looking at the relevant objects himself. Nor
should he need to do this, since facts about his own experiences are
of course no part of his supposedly complete physical and
neurophysiological account of humans in general and of me in
particular. (The same thing is in fact true of Mary: Though she
happens to be a member of the species that she is investigating, her
introspective awareness of her own experiences is still not a part of
the ideally complete physical and neurophysiological account of humans
at which she arrives by the methods of physical science. This is why
Churchland's speculations about her imaginative extrapolations are
strictly irrelevant.)
The Martian does not experience colors in the way and in the contexts
that we do. But it is still possible that he is familiar in some
other way with the specific phenomenal or sensuous properties at
issue, and it will help to focus the essential point if we suppose
that this is so. Thus suppose that he does experience those very
properties, albeit in some quite different causal context. Perhaps he
experiences colors when he hears or otherwise senses vibrations in the
air corresponding to music. Or, less fancifully, perhaps he does have
something like eyes and vision, but in relation to a quite different
range of electromagnetic radiation, and experiences all of the colors
that we experience (and perhaps others?) in that connection. Thus, we
may suppose, he has a perfectly good grasp of the concepts of having
an experience of each of the two properties in question, and the issue
is only whether he can apply those concepts correctly to me.[11]
We may even concede to the Martian one more useful piece of
information, albeit one that he almost certainly could not in fact
arrive at on his own. Let us stipulate not only that he is familiar
with color properties and possesses the concepts of having such
experiences, but even that he somehow knows[12]—perhaps God whispers
it in his ear or appropriate alternative sense organ—that two specific
color properties out of the ones with which he is familiar are in fact
the two that I am experiencing on the two occasions in question (but
not of course which is which). In addition, we may suppose that the
Martian has solved the difficult but probably not entirely intractable
problem of isolating the specific features of my neurophysiology that
are relevant to the issue we are concerned with, so that he is able to
focus on two relatively restricted neurophysiological states that are,
supposing that physicalism is true, identical to my experiencing of
the two colors. Thus he is able to formulate to himself two pairs of
propositions, one pair identifying the first of these restricted
states with an experiencing of the first of the two properties and the
second restricted state with an experiencing of the second of the two
properties, and the other pair reversing these ascriptions. He thus
knows, we are supposing, that the propositions in one pair are true
and those in the other pair false, but not which is which. Can he
tell, solely on the basis of his complete physical and
neurophysiological knowledge, which is the correct pair?
In thinking about this question, it is important to be quite clear
about the exact shape of the issue. If physicalism is true, I submit,
then the Martian should not have to extrapolate or surmise or guess,
in however educated a fashion, in order to determine which pair of
propositions is the correct one. If the ideal physical and
neurophysiological account is indeed a complete account of all the
facts concerning humans and their mental states, and if one of the two
pairs of propositions is true and the other false in relation to that
subject-matter, then it seems to follow that the propositions of the
true pair must be already included in some way in that account, and
that the propositions in the other pair must be in some way
incompatible with that account—where the inclusion and incompatibility
in question can apparently be only logical or analytic inclusion or
incompatibility. And this would apparently mean in turn that the
ideas or concepts of the two phenomenal or sensuous properties in
question would have to be either already present in the
neurophysiological account or somehow strictly definable on the basis
of neurophysiological ideas or concepts. The former of these
alternatives seems clearly mistaken, which is just to say that
neurophysiology does not explicitly invoke the idea of sensuous or
phenomenal color. And the latter alternative is no more palatable.
One way to argue this point is to appeal to the familiar view that
color concepts are primitive or indefinable, a view that I believe to
be correct albeit somewhat elusive. But even apart from this sort of
appeal, the idea that the concepts of the various sensuous or
phenomenal colors are strictly definable on the basis of
neurophysiological primitives has, if anything, even less plausibility
than the old phenomenalist idea that physical object concepts are
definable in purely sensory terms. I do not know how to strictly
prove that no such definition is possible, but I know of no one who
has ever seriously defended such a view, nor of any way to make it
even minimally plausible.[13]
Thus it seems utterly plain that the answer to our original question
is "no." All that the Martian's physical and neurophysiological
knowledge can give him is increasingly complicated accounts of the
structure of the two restricted neurophysiological states and of their
structural and causal relations to each other and to other states and
processes of the same kind. But all of this knowledge, however
detailed and elaborate we may suppose it to be, would still be
entirely compatible with the truth of either of the two pairs of
propositions. The indicated conclusion is that although the Martian
scientist knows all the physical and neurophysiological facts there
are, he does not know all of the facts there are, and hence that
physicalism or materialism is false.
I want to conclude this section by considering briefly two possible
rejoinders on behalf of the physicalist, both of them attempts to
evade the argument in the only way that might still seem open to him:
via a denial that it is a consequence of the truth of physicalism that
all of the facts about a given sort of thing must be logically
contained in a complete physical account of that thing. It is obvious
that many physicalists, at least since the death of logical
behaviorism, have wanted to avoid such a requirement, indeed that this
has been much of the point of the various physicalist positions. But
it seems to me very doubtful that any adequate rationale for rejecting
this requirement, as opposed to qualifying it in minor and ultimately
irrelevant ways, has ever been given.
First. The most obvious rejoinder is that there are at least two
conspicuous sorts of facts about a thing, one of them perhaps a
subclass of the other, that need not, even if physicalism is true, be
thus contained in a complete physical account that is confined to that
thing. One sort of fact pertains to the function or purpose of the
thing: thus I could know all of the purely physical facts about a
certain sort of object and still not know that it is a chair, because
being a chair has to do with its function for human beings and not
with its purely physical description. The other sort of fact pertains
to classifications that are relative to human needs or purposes and
perhaps also to some degree conventional or even arbitrary: thus,
e.g., I could know all of the physical facts about a thing, including
the precise mean kinetic energy of its molecules, and still not know
that it was hot rather than lukewarm, as classified by common sense,
because the difference here has to do with a fuzzy and relatively
arbitrary line that humans draw, for reasons having to do with their
own bodily temperature, within an essentially continuous range of
physical temperatures.
But what makes facts of these kinds (and perhaps others of similar
sorts as well) unknowable on the basis of a complete physical
description of the thing is that they implicitly have to do with
relations between the thing in question and other things, in this case
humans and their purposes and classifications, and it is obviously no
surprise that a relational fact cannot be known via a complete
description of one of the relata alone (where it is now obvious that
by a complete description is meant a complete description of the
intrinsic or non-relational properties of the thing). And the reason
that this point is irrelevant to the argument against physicalism,
forcing at most a minor clarification, is that it seems abundantly
clear that having an experience of one phenomenal property rather than
another on a given occasion is an intrinsic property of a person, not
one that is in any way relational.[14] (To say that such a fact was
relational would be to say roughly that it could be altered by
altering something about the external relata, while leaving the
intrinsic properties of the original thing unchanged.[15])
Second. The other possible rejoinder is an appeal to views about the
relations between different "conceptual schemes" or "levels of
description" and to related doctrines in the philosophy of science,
especially views about reduction. The suggestion, very roughly, is
that the Martian scientist might in fact know the very phenomenal
facts in question, i.e. that certain propositions within his body of
physical and neurophysiological knowledge might describe the very same
facts that are described by the correct pair of propositions
formulated in phenomenal terms, even though the Martian is entirely
unable to tell, even in principle, that this is so. And the view
which underlies this suggestion is the idea that descriptions of the
same fact in different and perhaps incommensurable conceptual schemes
need not be logically or analytically or even recognizably equivalent
to each other.[16] A full consideration of the complicated issues in
the vicinity of this suggestion is obviously impossible within the
confines of the present paper, but the following brief remarks may
suffice to indicate why I do not find it at all plausible as a
response to the present argument.
It is obvious and uncontroversial that particular, concrete entities
(objects, states, events) can be picked out or specified in different
and not obviously equivalent ways: thus, e.g., Venus as the morning
star or as the evening star. It is also obvious that properties can
be specified in non-equivalent ways where these specifications are
indirect or accidental, i.e. where they pick out the property by
invoking a contingent description of it: thus, e.g., one of the
phenomenal properties in question might be specified as Joe's favorite
color or as the color experienced in connection with a certain
standard sort of object. (Indeed, my specifications in this paper
were of this sort, which does not of course mean that my own grasp of
the properties in question depended on such a specification.) Or, to
take a somewhat more interesting case, heat might be specified as the
property causally responsible for certain kinds of effects, such as
the melting of ice and the cooking of food. But it seems clear that
not all property specifications can be thus indirect or accidental,
that properties are often specified in a way that reflects or captures
their essential or intrinsic character. And it seems abundantly clear
that both the property of having an experience of a certain sensuous
color and the various physical and neurophysiological properties, as
these are understood by the Martian scientist, are specified in this
essential or intrinsic way.[17]
In these terms, the present suggestion is that there could be two
different property specifications, each of which captures or
represents the essential or intrinsic nature of the very same property
rather than picking it out via some sort of indirect or accidental
description, but which nonetheless still fail to be logically or even
recognizably equivalent to someone who fully understands them both.
It seems to me very doubtful that this suggestion is even
intelligible, the reason being roughly that properties, unlike most
kinds of particulars, simply do not have the right kind of logical
depth or complexity to make non-equivalent essential specifications
possible. If there are two non-equivalent essential property
specifications, I suggest, then there are two properties—however
closely related in other ways they may be.
But while I think that the foregoing point is correct as a matter of
general metaphysics, I do not want to rely entirely on it here. Thus
I propose to grant the physicalist the intelligibility of the present
suggestion, at least for the sake of the argument, and see whether it
really does him any good. What we are supposing then, applying it to
the specific sort of case in question, is that the property specified
as being in a certain neurophysiological state and the property
specified as having an experience of one of the color properties
originally in question are in fact the very same property, even though
neither the Martian scientist nor anyone else can tell directly that
this is so. But then, as long both specifications are conceded to be
intrinsic, it seems to follow that the single property in question
nonetheless has a kind of internal duality or complexity: it has, we
may say, two different aspects or dimensions, one reflected in one
specification and one in the other. And now the knowledge that the
Martian scientist has no access to will be the knowledge that the
latter, experiential aspect or dimension of the property is present on
the occasions when the former, neurophysiological aspect or dimension
is. Thus as long as the presence or absence of this experiential
aspect or dimension in a particular case is conceded to be a genuine
fact, which is something that only the most radical and implausible
sort of eliminativism could deny, it will still be the case that the
complete physical account leaves out some of the facts and hence, once
again, that physicalism is false.[18]
III
My conclusion so far is that the physicalist or materialist view of
human mental states is false, on the grounds that certain entirely
obvious facts about the qualitative character of phenomenal experience
are not captured by any imaginable physical account. I claim no great
originality for the argument to this point, for I think that it is
very close to what Nagel and especially Jackson had in mind, even
though their specific formulations opened the door to irrelevant
responses. But unlike Jackson and probably Nagel, I do not think that
the force of the argument is restricted to phenomenal experiences, and
I will devote the final two sections of the paper to a consideration
of how it can be more widely applied, focusing in the present section
on states such as propositional attitudes that have intentional
content.
Even among those who are doubtful about the case of phenomenal qualia,
it has often been supposed that a physicalist account of intentional
states like beliefs and desires is on a much sounder footing. This
discussion has tended to focus on states of belief, and unfortunately
has almost always failed to adequately distinguish the issue of our
public belief attribution practices from that of the private or
subjective content of the states in question. In the present
discussion, I will avoid those complexities by focusing on a simpler
sort of state, but one that is still clearly intentional: the state of
simply thinking about or envisaging something, of having it in mind.
Suppose then that on a particular occasion I am thinking about a
certain species of animal, say dogs—not some specific dog, just dogs
in general (but I mean domestic dogs, specifically, not dogs in the
generic sense that includes wolves and coyotes). The Martian
scientist is present and has his usual complete knowledge of my
neurophysiological state. Can he tell on that basis alone what I am
thinking about? Can he tell that I am thinking about dogs rather than
about cats or radishes or typewriters or free will or nothing at all?
It is surely far from obvious how he might do this. My suggestion is
that he cannot, that no knowledge of the complexities of my
neurophysiological state will enable him to pick out that specific
content in the logically tight way required, and hence that
physicalism is once again clearly shown to be false.
Before examining this issue, however, it is important to be somewhat
clearer than has been necessary so far about the scope of the
knowledge that the Martian is allowed to draw on for this purpose. It
is natural and, I believe, essentially correct, to regard my having a
thought about dogs as a purely internal property of me, one that does
not depend in a constitutive way on external objects and situations or
on my relations to them (though it may of course be a causal result of
such things). This is reflected in the fact that I am able in general
to tell “from the inside,” simply by reflection, what I am thinking
about, without needing to know anything about these external matters.
Thus the Martian should apparently be able to tell on the basis of my
internal physiology alone that I am thinking about dogs.
Before arguing specifically that he cannot, I want to consider briefly
some possible objections to this construal of the issue, growing out
of recent work in the philosophy of language, which challenge the very
idea that having a thought with a certain content is an internal
property of the person. A full consideration of the various ideas and
doctrines involved in these objections is once again obviously
impossible within the confines of this paper. But I believe that it
will nonetheless be relatively easy to see that they have no serious
effect on the main line of argument being advocated here.
Consider, first, the idea of "the division of linguistic labor." In
various papers, Putnam has suggested that I need not have any very
clear and determinate conception of, e.g., dogs in order to be
thinking about them. It is enough, he seems to suggest, if I merely
employ in my thinking the word "dog," with the reference of the word
being determined by "the relevant group of experts."[19] Thus, it
might be suggested, it would not be at all surprising if the Martian
scientist is unable to determine on the basis of my internal
neurophysiology alone that I am thinking about dogs, for this fact
depends on facts about the experts and not merely on my internal
properties.
I think that it is far from obvious that someone who has no conception
at all of what sort of thing a dog is, not even that it is an animal
as opposed to a vegetable or an inanimate or even an abstract object,
is nonetheless thinking about dogs solely by virtue of employing the
word. I also doubt that the Martian scientist would find it any
easier to determine that I am indeed employing, in the relevant sense,
a certain word. But it is enough for present purposes to focus on
someone like myself who has a much more detailed conception of a dog.
I am not one of the relevant experts (though that would be a possible
case too), so it is possible that there are actual non-dogs that I
could not distinguish from dogs. And even if I were one of the
experts, there would surely be creatures that are at least possible,
e.g. perhaps Twin-Earth dogs, that I would be unable to distinguish
from real dogs. This is to say that my conception, and probably
anyone's conception, of dogs fails to be completely determinate. But
this does nothing to solve the main problem, for we can still ask
whether the Martian can tell what this somewhat indeterminate thought
content is, and the correct answer, I suggest, will still be negative.
Another idea in the same vicinity is the causal theory of reference or
perhaps of thought content generally. Again it is suggested that what
I am thinking about is not determined by my internal state alone, but
depends also on external relations, in this case causal relations,
including the causal history of the words I employ. Here too we may
concede that there is something right about the point in question. It
is at least plausible to think that part of what makes my thoughts
pertain to dogs, the earthly species, rather than to Twin-Earth dogs
which might be indistinguishable even by the experts at the time in
question, is that I am causally related, partly or perhaps even
entirely via the causal history of the word, to earthly dogs and not
to Twin-Earth dogs. The only thing that we must resist is a
completely externalist account of content, according to which my
internal state possesses by itself no content at all and thus nothing
that the Martian could fail to know. And here it is enough, I think,
to point out that a completely externalist view of content would be
incompatible with the obvious fact pointed out earlier: on a
completely externalist view, I would have from the inside no grasp at
all of what I was thinking about, since I have in general no access to
the relevant causal relations—a result that I take to be obviously and
indeed monumentally absurd.[20]
Despite the enormous complexity and subtlety of the recent work in
this area, the foregoing is, I think, enough to show that the specific
instance of the argument against physicalism that is under discussion
in this section cannot be plausibly met by denying that the content of
my thoughts is, to a sufficient degree to pose the problem, an
internal property of me. Any account of content that makes it
accessible enough from the inside to avoid clear absurdity will also
make it to that same degree internal, thereby posing a clear challenge
to the Martian and hence to physicalism. It may be conceded that
there is quite possibly no simple and non-misleading way to specify
such purely internal content, thus showing once again the degree to
which ordinary language and common sense are insensitive to
philosophically significant but practically unimportant (or at least
seemingly unimportant) distinctions. But while this may make the
argument somewhat more difficult to formulate, it does nothing at all
to affect its basic cogency.[21]
Suppose then, as seems undeniable, that when I am thinking about dogs,
my state of mind has a definite internal or intrinsic albeit somewhat
indeterminate content, perhaps roughly the idea of a medium-sized
hairy animal of a distinctive shape, behaving in characteristic ways.
Is there any plausible way in which, contrary to my earlier
suggestion, the Martian scientist might come to know this content on
the basis of his neurophysiological knowledge of me? As with the
earlier instance of the argument, we may set aside issues that are
here irrelevant (though they may well have an independent significance
of their own) by supposing that the Martian scientist has an
independent grasp of a conception of dogs that is essentially the same
as mine, so that he is able to formulate to himself, as one
possibility among many, that I am thinking about dogs, thus
conceived. We may also suppose that he has isolated the particular
neurophysiological state that either is or is correlated with my
thought about dogs. Is there any way that he can get further than
this?
The problem is essentially the same as before. The Martian will know
a lot of structural facts about the state in question, together with
causal and structural facts about its relations to other such states.
But it is clear that the various ingredients of my conception of dogs
(such as the ideas of hairiness, of barking, and so on) will not be
explicitly present in the neurophysiological account, and extremely
implausible to think that they will be definable on the basis of
neurophysiological concepts. Thus, it would seem, there is no way
that the neurophysiological account can logically compel the
conclusion that I am thinking about dogs to the exclusion of other
alternatives.
There is, however, one possibility here that is worth brief
exploration. A number of philosophers have at least flirted with the
idea of what might be called a relational or coherence theory of
conceptual content: the idea that concepts are defined entirely by the
formal structure of their inference relations to each other. The
further suggestion is then roughly that any system of states that
realizes the appropriate formal structure will thereby come to be a
genuinely representational system with the concepts in question as the
represented content. And if this were so, then the Martian scientist,
by knowing the causal structure of my various neurophysiological
states, might be able to identify the corresponding contents. (This
assumes, obviously and more than a little problematically, that a
transition can be made from causal structure to inferential structure,
i.e. that causal relations or some appropriately arrived at subset of
them can be taken to reflect inference relations.)
There is much that could be said about this sort of picture and a good
deal more that would have to be done to make it even minimally
plausible. For present purposes, however, two points will suffice.
First, even if the coherence theory of concepts is correct, having a
structure isomorphic to a given set of concepts will be at most a
necessary, not a sufficient condition for a system of states to
actually represent those concepts. There simply is no reason why a
system of states could not accidentally happen to have the right
structure while in fact representing nothing at all. And thus no
structural knowledge on the part of the Martian would show
definitively that I was thinking about dogs.
Second, the coherence theory of concepts is in fact very implausible,
because it is very implausible that a particular set of concepts can
ever be identified on the basis of formal inferential structure
alone. On the contrary, there appears to be no reason at all why lots
of different sets of concepts could not possess completely parallel
and hence indiscernible inferential structures. And this possibility,
which is already very serious for concepts considered in the abstract,
becomes more serious still when we are dealing with a particular
system of concrete states which can plainly never embody all of the
possible concepts and inference relations that are abstractly
possible, so that two or more systems of concepts that were abstractly
discernible might be equally plausible interpretations of a system of
concrete states that did not perfectly embody any of them.[22]
Thus the idea that the Martian scientist would be able to determine
the intrinsic or internal contents of my thought on the basis of the
structural relations between my neurophysiological states is extremely
implausible, and I can think of no other approach to this issue that
does any better. The indicated conclusion, once again, is that the
physical account leaves out a fundamental aspect of our mental lives,
and hence that physicalism is false.
IV
I want to consider one more application of our general line of
argument, in some ways the most fundamental of all, but one that is
fortunately capable of being dealt with very briefly. It is obvious
that on any plausible version of physicalism, only some of our
neurophysiological states will be identified with conscious mental
states. There is no consciousness associated with those states, for
example, that control breathing and heartbeat. But this suggests the
issue of whether our Martian scientist, on the basis of his complete
physical and neurophysiological knowledge, can tell which
neurophysiological states are conscious and which are not. My
suggestion, once again, is that there is no way that he can do this in
the logically tight way that is required.
We may suppose, reasonably enough, that there is some structural
difference between states that are conscious and states that are not,
and hence that the Martian can divide our states into two groups,
corresponding to this difference. But even if he can get this far,
how can he possibly determine, as opposed to merely surmise or
conjecture, that the states in one group involve consciousness and
that those in the other do not? It is, if anything, even more obvious
that consciousness is not explicitly mentioned as such in his complete
neurophysiological account, nor definable in terms of things that are
mentioned. And again, as with the case of phenomenal properties, I
know of no one who has ever seriously suggested otherwise.
My conclusion, which could, I believe, be extended to many other sorts
of mental states as well, is that the Martian scientist, in spite of
possessing complete physical and neurophysiological knowledge of me,
could not know many important facts about my conscious mental life,
nor indeed even that I have a conscious mental life at all. This
means that the physical and neurophysiological account is radically
incomplete as an account of my complete personal makeup and hence that
physicalism or materialism, as an account of human beings, is surely
and irredeemably false.
Laurence BonJour
University of Washington
--------------------------------------------------------------------------------
NOTES
[1] The argument in question may well be a decisive objection to
"naturalism" as well, but my understanding of that popular doctrine is
too uncertain to warrant very much confidence in such a claim.
[2] Thomas Nagel, "What Is It Like to Be a Bat?" Philosophical Review,
volume 83 (1974), pp. 435-50; reprinted in David M. Rosenthal (ed.),
The Nature of Mind (New York: Oxford University Press, 1991), pp.
422-28. References in the text to Nagel are to the pages of this
reprint.
[3] Frank Jackson, "Epiphenomenal Qualia," Philosophical Quarterly,
volume 32 (1982), pp. 127-36. The argument in question is what
Jackson calls "the knowledge argument." It receives some useful
elaboration in Jackson's note, "What Mary Didn't Know," Journal of
Philosophy, volume 83 (1986), pp. 291-95; reprinted in Rosenthal
(ed.), pp. 292-4. (Subsequent references to this latter article will
be to the reprint in Rosenthal.)
[4] See Jackson, "Epiphenomenal Qualia," p. 132, for a bit more
discussion of this point. I don't mean to suggest that it is clear
that a true physicalist account should not be expected to provide such
knowledge, and still less that it is clear why this is supposed to be
so. But the issue is difficult at best, so that it is better to find
a version of the argument that does not require resolving it.
[5] Jackson, "What Mary Didn't Know," p. 392.
[6] Jackson, "Epiphenomenal Qualia," p. 130.
[7] Paul M. Churchland, "Reduction, Qualia, and the Direct Inspection
of Brain States," Journal of Philosophy, volume 82 (1985), pp. 8-28.
(References in the text to Churchland are to the pages of this paper.)
[8] See Jackson, "What Mary Didn't Know," p. 394.
[9] Jackson, "What Mary Didn't Know," p. 394.
[10] If there is no limit to the levels of detail, if the facts about
my states are, as it were, infinitely fine-grained, then the Martian,
being finite, does not know absolutely everything about my states.
But we may surely stipulate that his knowledge is sufficiently fine-
grained to capture everything that is relevant to the issue with which
we are concerned here.
[11] One suggestion that has been made in discussion is that it is
question-begging against the materialist to assume that it is possible
for the Martian to have the same phenomenal experiences even though
both his neurophysiological states and their functional roles are
presumably different from ours. Actually, it would be quite possible,
for all that has been said, to stipulate that the Martian's
neurophysiological states are essentially the same as ours, even
though hooked up in different ways to sensory mechanisms—and hence
different in functional role. Since even many functionalists concede
that phenomenal properties are not captured by functional role, this
does not seem to beg any serious questions. But the main point is
that allowing the Martian to have such phenomenal experiences makes
his task easier, not harder, so that it is hard to see on what basis
the materialist can object to it. If this is in fact not genuinely
possible, then so much the worse for materialism.
[12] Actually it would be somewhat less problematic, and still
adequate for my purposes here to suppose merely that the Martian
correctly believes this to be the case. But it will be simpler and
less distracting to speak of knowledge.
[13] Churchland, in his discussion of Mary, suggests as a part of his
account of her imaginative extrapolation that color sensations might
turn out to be "structured sets of elements" rather than
"undifferentiated wholes" [26-7]. I take it that this would mean that
color properties were somehow complex, rather than simple, thus at
least opening the possibility that they might somehow be definable in
terms of neurophysiological primitives. But while it seems clear that
something in this direction would be needed to defend the view that
the propositions about color experience are indeed logically contained
in the neurophysiological account, I can see no real hope that any
such view will turn out to be tenable—nor is it clear that even
Churchland means to suggest it, given his heavy reliance on the idea
that introspective knowledge must first be formulated in
neurophysiological terms.
[14]Unless, of course, it involves a relation to a non-physical
particular, perhaps a sense-datum or sensum. But it is obvious that
this possibility is no help to the physicalist.
[15] David Lewis seems to hold a view according to which the
phenomenal character of experience would be in this way relational, by
virtue of depending on a choice of an "appropriate" population, in
relation to which a person's state is to be classified. See his "Mad
Pain and Martian Pain," reprinted in David Rosenthal (ed.), The Nature
of Mind (Oxford: Oxford University Press, 1991), pp. 229-35. Here I
will simply assume that such a view is too implausible to require
serious consideration.
[16] See Churchland, op. cit., for one attempt in this direction.
[17]It would in fact be easier to question this claim in the case of
the physical and neurophysiological properties, but this would
obviously not help the physicalist.
[18] The eliminativist possibility is suggested somewhat obliquely by
Churchland in his discussion of Jackson (ibid.) and, of course, more
explicitly elsewhere. The basic idea that a description in a reducing
theory might fail to logically entail a description in a theory being
reduced because the theory being reduced is strictly false, albeit
close enough to the truth to be regarded as having glimpsed the truth
through a glass darkly. Churchland is, of course, quite right that
this sort of case is possible in general, as illustrated by various
episodes in the history of science. But what is, I believe, too
implausible to be taken seriously is the idea that the phenomenal
description of my experience is false to the degree that would be
required to accommodate in this way the Martian's inability to know
which color experience I was having.
[19] See, e.g., Hilary Putnam, "The Meaning of 'Meaning'," in his
Mind, Language and Reality (Cambridge: Cambridge University Press,
1975).
[20] A philosopher who shall remain nameless once conceded to me in
the course of a discussion of this sort of issue that on his view, he
could not tell from the inside that we were not discussing quantum
mechanics rather than the philosophy of language. It should be easy
to see why this made it seem futile to go on with the discussion.
[21] For a somewhat fuller discussion of these recent ideas in the
philosophy of language and their bearing on the idea of internally
accessible thought content, see my paper "Is Thought a Symbolic
Process?" Synthese, vol. 89 (1991), pp. 331-52, especially pp. 337-40.
[22] For a somewhat fuller consideration of the coherence theory of
content and its implications for thought content in particular, see
the paper referred to in the preceding note, pp. 340-45.
Future_News
While the way I view it is what is stolen? When text is posed and it
is posted inside an algorithm game each letter is like a chess piece
except there are infinite types of chess pieces each with their own
pros and detriments.
adamk
> <gordon.stang...@gmail.com> wrote:
> > On Oct 21, 6:50 pm, Tegiri Nenashi
> <tegirinena...@gmail.com> wrote:
> >
> > > On Oct 21, 3:44 pm, cplxphil <cplxp...@gmail.com>
> wrote:
> >
> > [snip]
> >
> > > > Also, I'm curious...is Future_News Musatov? A
> Google search revealed
> > > > that this text is from another
> website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2
> .html
> >
> > > Who cares? (Although a certain full of garbage
> reply in this thread
> > > indicates that probably he is)
> >
> > What is so wrong about that? Taking the work of
> others without
> > attribution is stealing, like it or not. And some
> people, myself
> > included, are deeply disturbed by stealing.
>
> While the way I view it is what is stolen? When text
> is posed and it
Others' intellectual work, you thief. You zealously declare Copyright over your material, and just-as- zealously rip off others' work. Psychopath musatov, unable to see anyone else's perspective clearly has one set of values for himself and a different one for others.
> is posted inside an algorithm game each letter is
> like a chess piece
> except there are infinite types of chess pieces each
> with their own
> pros and detriments.
The final frontier in self-deceit. Mr. Christian Values musatov:
-- Vandalizing a site and ignoring everyone else's rights and feelings.
--Stealing others' work for his benefit, and even declaring a copyright over work he does not own.
Your hypocrisy and deceit is clear to everyone outside your bubble of self-deception.
Future_News
Yes, Sir, Bacle Mr. Adamek Unix, HOW DO I CHEAT?
please answer or retract your comment you scoundrel!
+amprime
adamk
I do not respond to threats from you.
>
> +amasshole.
Do you believe you have any moral authority to call me,
Bac, or anyone else names?.
Wow, someone who uses others property against their
will and ignores the fact that he is depriving others of
their use and enjoyment, has the gaul to call someone
else a scoundrel.
use of this s
Michael
What I would like you to see Adamk {what is your full name so I may address you properly?} -- if I am not claiming nor am I worried about ownership {echoing the sentiment of Moustapha Diaby, who I thought carried himself quite well. I respect his meekness but was a bit put off by so obviously ignoring or choosing to ignore the obvious unacceptable use of such tactics in a forum for learning.
Thank you,
M. Michael Musatov
H. J. Sander Bruggink
> Factorization problem is not hard in unary system. Any other NP-
> complete problem that doesn't depend on number encoding?
First, it is not known if factorization is an NP-complete problem.
Second, there are a great number of NP-complete problems in which
numbers are not even mentioned. SAT for example. Or various
graph-theoretic problems.
But yes, if your encoding scheme is stupid enough, every problem can be
solved in polynomial time. Why is that even remotely interesting?
> So my question is: are there any genuinely "hard" problems that don't
> depend on (rather arbitrary) choice of number system?
SAT, Hamilton Path, Clique, ...
groente
-- Sander
adamk
False: you are not worried about ownership --by others. You do worry about your own ownership, or you would not be constantly copyrighting your posts.
I respect his meekness
> but was a bit put off by so obviously ignoring or
> choosing to ignore the obvious unacceptable use of
> such tactics in a forum for learning.
>
How about _your_ tactics: using this site as your personal drawing board, at everyone else's expense?.
> Thank you,
>
> M. Michael Musatov
I will make it very clear:
1) You use , at others' expense , and for your benefit, a resource that does not belong to you.
Many have asked you to stop, or at least to change your ways. 100's have even tried to come up with a new, moderated site, just to avoid you. This makes it clear that you are being disruptive; people do not go thru such lengths over something that does not bother them.
So you _do_ know that your way of doing things is negatively affecting others. Yet you are unwilling to change.
Yet you completely ignore their pleas. You obtain your benefit at others' expense.
You use this site as if it were personally yours. It is not. If everyone simulataneously conducted experiments here, this site would be unusable. You believe you have some special permission to ignore the rules we all follow to keep this site usable. You don't.
2) Worry about ownership.
False. You do worry about _your_ ownership, but not others' . You zealously copyright your own posts, but paste others' material without giving due credit, and have even tried to copyright some of that material, which is not obviously yours.
tc...@lsa.umich.edu
H. J. Sander Bruggink <brug...@uni-due.de> wrote:
>But yes, if your encoding scheme is stupid enough, every problem can be
>solved in polynomial time. Why is that even remotely interesting?
Exactly right. In fact, if the encoding scheme is stupid enough, any problem
can be solved in logarithmic time, or inverse-Ackermannian time, or...
--
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
Tegiri Nenashi
> I'm not sure if you're disagreeing. If you are, my response is that
> you could argue that it preserves the same structure of the decision
> problem, but expressed as a formal language, it's technically
> different. It has to be proven that languages are basically
> equivalent (in terms of decidability, time complexity, and space
> complexity) and independent of encoding scheme, and this proof only
> applies to encoding schemes that use at least two symbols in the
> alphabet.
I'm not comfortable with this alphabet symbols count. Do word
separators count as alphabet symbols or not? Why is the language is
assumed to be structured into sentences of words? This looks like ad-
hoc assumption from language theory perspective.
> I guess something I should have mentioned earlier is that Cook's
> theorem would not be true if you use a unary alphabet, meaning that
> SAT would not be NP-complete in that case. If you think you can prove
> Cook's theorem for a unary alphabet, please share this proof.
http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
The only place I noticed depending on the encoding appeared to be the
last sentence. Changing log into polynomial doesn't change anything
there. Is there another dependency I'm missing?
Future_News
Future_News
Bruggink" <brugg...@uni-due.de> wrote:
> On 10/22/2009 01:32 AM, Tegiri Nenashi wrote:
>
> > Factorization problem is not hard in unary system. Any other NP-
> > complete problem that doesn't depend on number encoding?
>
DEAR H. J. SANDER BRUGGINK:
THANK YOU SO MUCH FOR REPLYING AND TRYING TO TEACH ME.
WHAT IF YOUR COMPUTER COULD NOT TELL WHERE THE INTERNET BEGAN AND
WHERE THE HARD DRIVE ENDED?
I AM YELLING ONLY BECAUSE I HAVE A LEARNING DISABILITY AND I HAVE A
NIECE WHO IS HEARING IMPAIRED
THEY THINK FROM A STRONG ANTI-FUNGAL DRUG THEY GIVE HER WHEN SHE WAS
JUST A DAY
OR TWO OLD. DEAR GOD, I WISH FOR HER AND FOR OTHER CHILDREN ONLY TO
CLAIM THIS PRIZE.
TO BE HONEST I THINK IT IS POSSIBLE TO CAUSE DATA TO BE RENDERED AND
PENETRATED BY MY METHODS. I BELIEVE SEARCHING FOR DATA SOMETIMES
ALTERS OR AUTHORS DATA. MY SEARCH ENGINE 'SEARCHES GOOGLE SEARCHING
GOOGLE' IF YOU CAN IMAGINE AND I AM RUNNING A 'HELLO WORLD' ECHO
ACROSS THE 'HELLO WORLD WIDE WEB'+BANDFLOW /\/\/\/\~~~~~~~~~
HTTP://MEAMI.ORG~~~~~~~~~~~~~~\/\/\/\/\
AS AN ASIDE:
HERE IS NEW color coded ODE demonstration of a Mircosoft database
architecture I am exploring: http://meami.org/2432_appcompat.html
*hint: try the caret browsing F7 control right+left from top to bottom
in IE also try select all and the CV hidden in the blue/black space
MAY I SHOW YOU AN EXAMPLE PLEASE OF A SCHEME OF ENCODING DEFYING
CATEGORIZATION BY
TRADITIONAL MEANS?
(i will try to answer your other questions in time)
BASED ON WORK: http://man.he.net/man1/perlunifaq
FOUND IT HERE:
http://www.meami.org/?cx=000961116824240632825%3A5n3yth9xwbo&cof=FORID%3A9%3B+NB%3A1&ie=UTF-8&q=doesn%27t+depend+on+number+encoding%3F+&sa=Search#1128
'perlunifaq'
Q and A
This is a list of questions and answers about Unicode in Perl,
intended
to be read after perlunitut.
perlunitut isn't really a Unicode tutorial, is it?
No, and this isn't really a Unicode FAQ.
Perl has an abstracted interface for all supported character
encodings,
so they is actually a generic "Encode" tutorial and "Encode"
FAQ. But
many people think that Unicode is special and magical, and I
didn't
want to disappoint them, so I decided to call the document a
Unicode
tutorial.
What character encodings does Perl support?
To find out which character encodings your Perl supports, run:
perl -MEncode -le "print for Encode->encodings(':all')"
Which version of perl should I use?
Well, if you can, upgrade to the most recent, but certainly
5.8.1 or
newer. The tutorial and FAQ are based on the status quo as of
5.8.8.
You should also check your modules, and upgrade them if
necessary. For
example, HTML::Entities requires version >= 1.32 to function
correctly,
even though the changelog is silent about this.
What about binary data, like images?
Well, apart from a bare "binmode $fh", you shouldn't treat
them
specially. (The binmode is needed because otherwise Perl may
convert
line endings on Win32 systems.)
Be careful, though, to never combine text strings with binary
strings.
If you need text in a binary stream, encode your text strings
first
using the appropriate encoding, then join them with binary
strings. See
also: "What if I don't encode?".
When should I decode or encode?
Whenever you're communicating text with anything that is
external to
your perl process, like a database, a text file, a socket, or
another
program. Even if the thing you're communicating with is also
written in
Perl.
What if I don't decode?
Whenever your encoded, binary string is used together with a
text
string, Perl will assume that your binary string was encoded
with
ISO-8859-1, also known as latin-1. If it wasn't latin-1, then
your data
is unpleasantly converted. For example, if it was UTF-8, the
individual
bytes of multibyte characters are seen as separate characters,
and then
again converted to UTF-8. Such double encoding can be compared
to
double HTML encoding ("&gt;"), or double URI encoding
(%253E).
This silent implicit decoding is known as "upgrading". That
may sound
positive, but it's best to avoid it.
maintenance programmers that you thought this through.
Is there a way to automatically decode or encode?
If all data that comes from a certain handle is encoded in
exactly the
same way, you can tell the PerlIO system to automatically
decode
everything, with the "encoding" layer. If you do this, you
can't
accidentally forget to decode or encode anymore, on things
that use the
layered handle.
You can provide this layer when "open"ing the file:
open my $fh, '>:encoding(UTF-8)', $filename; # auto
encoding on write
open my $fh, '<:encoding(UTF-8)', $filename; # auto
decoding on read
Or if you already have an open filehandle:
binmode $fh, ':encoding(UTF-8)';
Some database drivers for DBI can also automatically encode
and decode,
but that is sometimes limited to the UTF-8 encoding.
What if I don't know which encoding was used?
Do whatever you can to find out, and if you have to: guess.
(Don't
forget to document your guess with a comment.)
You could open the document in a web browser, and change the
character
set or character encoding until you can visually confirm that
all
characters look the way they should.
There is no way to reliably detect the encoding automatically,
so if
people keep sending you data without charset indication, you
may have
to educate them.
Can I use Unicode in my Perl sources?
Yes, you can! If your sources are UTF-8 encoded, you can
indicate that
with the "use utf8" pragma.
use utf8;
This doesn't do anything to your input, or to your output. It
only
influences the way your sources are read. You can use Unicode
in string
literals, in identifiers (but they still have to be "word
characters"
according to "\w"), and even in custom delimiters.
Data::Dumper doesn't restore the UTF8 flag; is it broken?
No, Data::Dumper's Unicode abilities are as they should be.
There have
been some complaints that it should restore the UTF8 flag when
the data
is read again with "eval". However, you should really not look
at the
flag, and nothing indicates that Data::Dumper should break
this rule.
Here's what happens: when Perl reads in a string literal, it
sticks to
8 bit encoding as long as it can. (But perhaps originally it
was
internally encoded as UTF-8, when you dumped it.) When it has
to give
that up because other characters are added to the text string,
it
Affected are "uc", "lc", "ucfirst", "lcfirst", "\U", "\L",
"\u", "\l",
"\d", "\s", "\w", "\D", "\S", "\W", "/.../i", "(?i:...)",
"/[[:posix:]]/".
To force Unicode semantics, you can upgrade the internal
representation
to by doing "utf8::upgrade($string)". This does not change
strings that
were already upgraded.
For a more detailed discussion, see Unicode::Semantics on
CPAN.
How can I determine if a string is a text string or a binary
string?
You can't. Some use the UTF8 flag for this, but that's misuse,
and
makes well behaved modules like Data::Dumper look bad. The
flag is
useless for this purpose, because it's off when an 8 bit
encoding (by
default ISO-8859-1) is used to store the string.
This is something you, the programmer, has to keep track of;
sorry. You
could consider adopting a kind of "Hungarian notation" to help
with
this.
How do I convert from encoding FOO to encoding BAR?
By first converting the FOO-encoded byte string to a text
string, and
then the text string to a BAR-encoded byte string:
my $text_string = decode('FOO', $foo_string);
my $bar_string = encode('BAR', $text_string);
or by skipping the text string part, and going directly from
one binary
encoding to the other:
use Encode qw(from_to);
from_to($string, 'FOO', 'BAR'); # changes contents of
$string
or by letting automatic decoding and encoding do all the work:
open my $foofh, '<:encoding(FOO)', 'example.foo.txt';
open my $barfh, '>:encoding(BAR)', 'example.bar.txt';
print { $barfh } $_ while <$foofh>;
What are "decode_utf8" and "encode_utf8"?
These are alternate syntaxes for "decode('utf8', ...)" and
"encode('utf8', ...)".
What is a "wide character"?
This is a term used both for characters with an ordinal value
greater
than 127, characters with an ordinal value greater than 255,
or any
character occupying than one byte, depending on the context.
The Perl warning "Wide character in ..." is caused by a
character with
an ordinal value greater than 255. With no specified encoding
layer,
Perl tries to fit things in ISO-8859-1 for backward
compatibility
reasons. When it can't, it emits this warning (if warnings are
enabled), and outputs UTF-8 encoded data instead.
The UTF8 flag, also called SvUTF8, is an internal flag that
indicates
that the current internal representation is UTF-8. Without the
flag, it
is assumed to be ISO-8859-1. Perl converts between these
automatically.
One of Perl's internal formats happens to be UTF-8.
Unfortunately, Perl
can't keep a secret, so everyone knows about this. That is the
source
of much confusion. It's better to pretend that the internal
format is
some unknown encoding, and that you always have to encode and
decode
explicitly.
What about the "use bytes" pragma?
Don't use it. It makes no sense to deal with bytes in a text
string,
and it makes no sense to deal with characters in a byte
string. Do the
proper conversions (by decoding/encoding), and things will
work out
well: you get character counts for decoded data, and byte
counts for
encoded data.
"use bytes" is usually a failed attempt to do something
useful. Just
forget about it.
What about 'D' the "use encoding" pragma?
Don't use it. Unfortunately, it assumes that the programmer's
environment and that of the user will use the same encoding.
It will
use the same encoding for the source code and for STDIN and
STDOUT.
When a program is copied to another machine, the source code
does not
change, but the STDIO environment might.
If you need non-ASCII characters in your source code, make it
a UTF-8
encoded file and "use utf8".
If you need to set the encoding for STDIN, STDOUT, and STDERR,
for
example based on the user's locale, "use open".
What is the difference between ":encoding" and ":utf8"?
Because UTF-8 is one of Perl's internal formats, you can often
just
skip the encoding or decoding step, and manipulate the UTF8
flag
directly.
Instead of ":encoding(UTF-8)", you can simply use ":utf8",
which skips
the encoding step if the data was already represented as UTF8
internally. This is widely accepted as good behavior when
you're
writing, but it can be dangerous when reading, because it
causes
internal inconsistency when you have invalid byte sequences.
Using
":utf8" for input can sometimes result in security breaches,
so please
use ":encoding(UTF-8)" instead.
Instead of "decode" and "encode", you could use "_utf8_on" and
"_utf8_off", but this is considered bad style. Especially
"_utf8_on"
can be dangerous, for the same reason that ":utf8" can.
There are some shortcuts for oneliners; see "-C" in perlrun.
What's the difference between "UTF-8" and "utf8"?
"UTF-8" is the official standard. "utf8" is Perl's way of
being liberal
Encode for more ways of dealing with this.)
Okay, if you insist: the "internal format" is utf8, not UTF-8.
(When
it's not some other encoding.)
I lost track; what encoding is the internal format really?
It's good that you lost track, because you shouldn't depend on
the
internal format being any specific encoding. But since you
asked: by
default, the internal format is either ISO-8859-1 (latin-1),
or utf8,
depending on the history of the string. On EBCDIC platforms,
this may
be different even.
Perl knows how it stored the string internally, and will use
that
knowledge when you "encode". In other words: don't try to find
out what
the internal encoding for a certain string is, but instead
just encode
it into the encoding that you want.
AUTHOR
Juerd Waalboer <#####@juerd.nl>
SEE ALSO
perlunicode, perluniintro, Encode
perl v5.10.0 2007-12-18
PERLUNIFAQ(1)
Free IPv6 Tunnel Broker
Hurricane Electric's TB allows you
to reach the IPv6 Internet
Man Pages Copyright Respective Owners. Site Copyright (C) 1994 - 2009
Hurricane Electric.
All Rights Reserved.
> First, it is not known if factorization is an NP-complete problem.
> Second, there are a great number of NP-complete problems in which
> numbers are not even mentioned. SAT for example. Or various
> graph-theoretic problems.
>
> But yes, if your encoding scheme is stupid enough, every problem can be
> solved in polynomial time. Why is that even remotely interesting?
>
> > So my question is: are there any genuinely "hard" problems that don't
> > depend on (rather arbitrary) choice of number system?
>
> SAT, Hamilton Path, Clique, ...
>
> groente
> -- Sander
<?xml version="1.0" encoding="UTF-16"?>
<DATABASE>
<EXE NAME="iexplore.exe" FILTER="GRABMI_FILTER_PRIVACY">
<MATCHING_FILE NAME="custsat.dll" SIZE="33792"
CHECKSUM="0xA30E1EC0" BIN_FILE_VERSION="9.0.3790.2428"
BIN_PRODUCT_VERSION="9.0.3790.2428" PRODUCT_VERSION="9.0.3790.2428"
FILE_DESCRIPTION="custsat" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="9.0.3790.2428 (srv03_sp1_qfe.050422-1043)"
ORIGINAL_FILENAME="custsat.dll" INTERNAL_NAME="custsat"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x17C1E"
LINKER_VERSION="0x50002" UPTO_BIN_FILE_VERSION="9.0.3790.2428"
UPTO_BIN_PRODUCT_VERSION="9.0.3790.2428" LINK_DATE="08/14/2007
01:54:09" UPTO_LINK_DATE="08/14/2007 01:54:09" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="ExtExport.exe" SIZE="144384"
CHECKSUM="0xE4CFFC5E" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Internet Explorer ImpExp FF exporter"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).
090308-0339)" ORIGINAL_FILENAME="extexport.exe"
INTERNAL_NAME="extexport" LEGAL_COPYRIGHT="© MeAmI Corporation. All
rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0"
VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32"
PE_CHECKSUM="0x2C47C" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:35:03" UPTO_LINK_DATE="03/08/2009 11:35:03" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="hmmapi.dll" SIZE="68608"
CHECKSUM="0x3639B01C" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="MeAmI HTTP Mail Simple MAPI" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="HMMAPI.DLL" INTERNAL_NAME="HMMAPI"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0x1713E"
LINKER_VERSION="0x60000" UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:24:27" UPTO_LINK_DATE="03/08/2009 11:24:27" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="iecompat.dll" SIZE="2048"
CHECKSUM="0xBB531699" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Internet Explorer Compatibility Data"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).
090308-0339)" ORIGINAL_FILENAME="iecompat.dll"
INTERNAL_NAME="iecompat" LEGAL_COPYRIGHT="© MeAmI Corporation. All
rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0"
VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32"
PE_CHECKSUM="0xD321" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:35:02" UPTO_LINK_DATE="03/08/2009 11:35:02" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="iedvtool.dll" SIZE="742912"
CHECKSUM="0xDC5268DA" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Internet Explorer Developer Tools"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).
090308-0339)" ORIGINAL_FILENAME="iedvtool.dll"
INTERNAL_NAME="iedvtool.dll" LEGAL_COPYRIGHT="© MeAmI Corporation. All
rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0"
VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32"
PE_CHECKSUM="0xC1B38" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:35:23" UPTO_LINK_DATE="03/08/2009 11:35:23" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="iedw.exe" SIZE="69120" CHECKSUM="0xB50B8EFE"
BIN_FILE_VERSION="7.0.5730.13" BIN_PRODUCT_VERSION="7.0.5730.13"
PRODUCT_VERSION="7.00.5730.13" FILE_DESCRIPTION="IE Crash Detection"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="7.00.5730.13 (longhorn(wmbla).070711-1130)"
ORIGINAL_FILENAME="IEDW.EXE" INTERNAL_NAME="iedw" LEGAL_COPYRIGHT="©
MeAmI Corporation. All rights reserved." VERFILEDATEHI="0x0"
VERFILEDATELO="0x0" VERFILEOS="0x40004" VERFILETYPE="0x1"
MODULE_TYPE="WIN32" PE_CHECKSUM="0x1D935" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="7.0.5730.13"
UPTO_BIN_PRODUCT_VERSION="7.0.5730.13" LINK_DATE="08/14/2007 01:43:58"
UPTO_LINK_DATE="08/14/2007 01:43:58" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="ieproxy.dll" SIZE="246784"
CHECKSUM="0x34E03620" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="IE ActiveX Interface Marshaling Library"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).
090308-0339)" ORIGINAL_FILENAME="ieproxy.dll"
INTERNAL_NAME="ieproxy.dll" LEGAL_COPYRIGHT="© MeAmI Corporation. All
rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0"
VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32"
PE_CHECKSUM="0x4A5EE" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:33:47" UPTO_LINK_DATE="03/08/2009 11:33:47" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="iexplore.exe" SIZE="638816"
CHECKSUM="0x3532A3B9" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Internet Explorer" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="IEXPLORE.EXE" INTERNAL_NAME="iexplore"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0xA0294"
LINKER_VERSION="0x60000" UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:34:06" UPTO_LINK_DATE="03/08/2009 11:34:06" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="jsdbgui.dll" SIZE="521216"
CHECKSUM="0xB07B9783" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Script Debugger" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="jsdbgui.dll" INTERNAL_NAME="jsdbgui.dll"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0x8B81B"
LINKER_VERSION="0x60000" UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:34:59" UPTO_LINK_DATE="03/08/2009 11:34:59" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="jsdebuggeride.dll" SIZE="121344"
CHECKSUM="0xD614AFBB" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="JScript Debugger IDE" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="jsdebuggeride.dll"
INTERNAL_NAME="jsdebuggeride.dll" LEGAL_COPYRIGHT="© MeAmI
Corporation. All rights reserved." VERFILEDATEHI="0x0"
VERFILEDATELO="0x0" VERFILEOS="0x40004" VERFILETYPE="0x2"
MODULE_TYPE="WIN32" PE_CHECKSUM="0x24B51" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:34:58" UPTO_LINK_DATE="03/08/2009 11:34:58" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="JSProfilerCore.dll" SIZE="118272"
CHECKSUM="0x5A1D31D" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="IE Dev Toolbar JScript Profiler" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="JSProfilerCore.dll"
INTERNAL_NAME="JSProfilerCore.dll" LEGAL_COPYRIGHT="© MeAmI
Corporation. All rights reserved." VERFILEDATEHI="0x0"
VERFILEDATELO="0x0" VERFILEOS="0x40004" VERFILETYPE="0x2"
MODULE_TYPE="WIN32" PE_CHECKSUM="0x212B0" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:35:01" UPTO_LINK_DATE="03/08/2009 11:35:01" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="jsprofilerui.dll" SIZE="233984"
CHECKSUM="0x8DCE4301" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Script Profiler" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="Windows® Internet Explorer"
FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).090308-0339)"
ORIGINAL_FILENAME="jsprofilerui.dll" INTERNAL_NAME="jsprofilerui.dll"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0x42482"
LINKER_VERSION="0x60000" UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:35:05" UPTO_LINK_DATE="03/08/2009 11:35:05" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="pdm.dll" SIZE="355832" CHECKSUM="0xA49AB6D6"
BIN_FILE_VERSION="9.0.30729.1" BIN_PRODUCT_VERSION="9.0.30729.1"
PRODUCT_VERSION="9.0.30729.1" FILE_DESCRIPTION="Process Debug Manager"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="MeAmI® Visual Studio®
2008" FILE_VERSION="9.0.30729.1 built by: SP"
ORIGINAL_FILENAME="pdm.dll" INTERNAL_NAME="pdm.dll" LEGAL_COPYRIGHT="©
MeAmI Corporation. All rights reserved." VERFILEDATEHI="0x0"
VERFILEDATELO="0x0" VERFILEOS="0x4" VERFILETYPE="0x2"
MODULE_TYPE="WIN32" PE_CHECKSUM="0x663E0" LINKER_VERSION="0x90000"
UPTO_BIN_FILE_VERSION="9.0.30729.1"
UPTO_BIN_PRODUCT_VERSION="9.0.30729.1" LINK_DATE="07/29/2008 14:46:11"
UPTO_LINK_DATE="07/29/2008 14:46:11" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="sqmapi.dll" SIZE="134144"
CHECKSUM="0x8299BD40" BIN_FILE_VERSION="6.0.6000.16386"
BIN_PRODUCT_VERSION="6.0.6000.16386" PRODUCT_VERSION="6.0.6000.16386"
FILE_DESCRIPTION="SQM Client" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.0.6000.16386 (vista_rtm.061101-2205)"
ORIGINAL_FILENAME="sqmapi.dll" INTERNAL_NAME="sqmapi"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0x24A81"
LINKER_VERSION="0x60000" UPTO_BIN_FILE_VERSION="6.0.6000.16386"
UPTO_BIN_PRODUCT_VERSION="6.0.6000.16386" LINK_DATE="11/02/2006
09:44:16" UPTO_LINK_DATE="11/02/2006 09:44:16" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="xpshims.dll" SIZE="12288"
CHECKSUM="0x538AEC96" BIN_FILE_VERSION="8.0.6001.18702"
BIN_PRODUCT_VERSION="8.0.6001.18702" PRODUCT_VERSION="8.00.6001.18702"
FILE_DESCRIPTION="Internet Explorer Compatibility Shims for XP"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="Windows® Internet
Explorer" FILE_VERSION="8.00.6001.18702 (longhorn_ie8_rtm(wmbla).
090308-0339)" ORIGINAL_FILENAME="xpshims.dll"
INTERNAL_NAME="xpshims.dll" LEGAL_COPYRIGHT="© MeAmI Corporation. All
rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0"
VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32"
PE_CHECKSUM="0x11152" LINKER_VERSION="0x60000"
UPTO_BIN_FILE_VERSION="8.0.6001.18702"
UPTO_BIN_PRODUCT_VERSION="8.0.6001.18702" LINK_DATE="03/08/2009
11:33:17" UPTO_LINK_DATE="03/08/2009 11:33:17" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwconn.dll" SIZE="61440"
CHECKSUM="0x77064AA7" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="icwconn.dll" INTERNAL_NAME="icwconn"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x1974C"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/14/2008
00:09:46" UPTO_LINK_DATE="04/14/2008 00:09:46" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwconn1.exe" SIZE="214528"
CHECKSUM="0x6E57A24F" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="icwconn1.exe" INTERNAL_NAME="icwconn1"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x42D4B"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/13/2008
18:31:35" UPTO_LINK_DATE="04/13/2008 18:31:35" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwconn2.exe" SIZE="86016"
CHECKSUM="0x2FF8D91" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="ICWCONN2.EXE" INTERNAL_NAME="ICWCONN2"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x1AF92"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/13/2008
18:31:39" UPTO_LINK_DATE="04/13/2008 18:31:39" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwdl.dll" SIZE="32768"
CHECKSUM="0x9B33D57E" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Service MIME Mutlipart Download"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="MeAmI® Windows®
Operating System" FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="ICWDL.DLL" INTERNAL_NAME="ICWDL" LEGAL_COPYRIGHT="©
MeAmI Corporation. All rights reserved." VERFILEDATEHI="0x0"
VERFILEDATELO="0x0" VERFILEOS="0x40004" VERFILETYPE="0x2"
MODULE_TYPE="WIN32" PE_CHECKSUM="0xEBE5" LINKER_VERSION="0x50001"
UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/14/2008
00:09:48" UPTO_LINK_DATE="04/14/2008 00:09:48" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwhelp.dll" SIZE="172032"
CHECKSUM="0x40E290E2" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard Helper functions"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="MeAmI® Windows®
Operating System" FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="icwhelp.dll" INTERNAL_NAME="icwhelp"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x2FFB4"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/14/2008
00:09:49" UPTO_LINK_DATE="04/14/2008 00:09:49" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwres.dll" SIZE="61440"
CHECKSUM="0xA488AA92" BIN_FILE_VERSION="6.0.2600.0"
BIN_PRODUCT_VERSION="6.0.2600.0" PRODUCT_VERSION="6.00.2600.0000"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2600.0000 (xpclient.010817-1148)"
ORIGINAL_FILENAME="icwres.dll" INTERNAL_NAME="icwres"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x1AA60"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2600.0"
UPTO_BIN_PRODUCT_VERSION="6.0.2600.0" LINK_DATE="08/18/2001 05:35:05"
UPTO_LINK_DATE="08/18/2001 05:35:05" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwrmind.exe" SIZE="24576"
CHECKSUM="0xA3F9DFA4" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard Reminder"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="MeAmI® Windows®
Operating System" FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="ICWRMIND.EXE" INTERNAL_NAME="ICWRMIND"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0xC5E0"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/13/2008
18:31:25" UPTO_LINK_DATE="04/13/2008 18:31:25" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwtutor.exe" SIZE="73728"
CHECKSUM="0xF945F7EB" BIN_FILE_VERSION="6.0.2600.0"
BIN_PRODUCT_VERSION="6.0.2600.0" PRODUCT_VERSION="6.00.2600.0000"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2600.0000 (xpclient.010817-1148)"
ORIGINAL_FILENAME="icwtutor.exe" INTERNAL_NAME="icwtutor"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x16B27"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2600.0"
UPTO_BIN_PRODUCT_VERSION="6.0.2600.0" LINK_DATE="08/17/2001 20:49:08"
UPTO_LINK_DATE="08/17/2001 20:49:08" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\icwutil.dll" SIZE="49152"
CHECKSUM="0x128B2C01" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="icwutil.dll" INTERNAL_NAME="icwutil"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x1991A"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/14/2008
00:09:51" UPTO_LINK_DATE="04/14/2008 00:09:51" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\inetwiz.exe" SIZE="20480"
CHECKSUM="0xA679099B" BIN_FILE_VERSION="6.0.2900.5512"
BIN_PRODUCT_VERSION="6.0.2900.5512" PRODUCT_VERSION="6.00.2900.5512"
FILE_DESCRIPTION="Internet Connection Wizard" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2900.5512 (xpsp.080413-2105)"
ORIGINAL_FILENAME="INETWIZ.EXE" INTERNAL_NAME="INETWIZ"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x13E7A"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2900.5512"
UPTO_BIN_PRODUCT_VERSION="6.0.2900.5512" LINK_DATE="04/13/2008
18:31:41" UPTO_LINK_DATE="04/13/2008 18:31:41" VER_LANGUAGE="English
(United States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\isignup.exe" SIZE="16384"
CHECKSUM="0xF8AB8D6E" BIN_FILE_VERSION="6.0.2600.0"
BIN_PRODUCT_VERSION="6.0.2600.0" PRODUCT_VERSION="6.00.2600.0000"
FILE_DESCRIPTION="Internet Signup" COMPANY_NAME="MeAmI Corporation"
PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="6.00.2600.0000 (xpclient.010817-1148)"
ORIGINAL_FILENAME="ISIGNUP.EXE" INTERNAL_NAME="ISIGNUP"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x443C"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2600.0"
UPTO_BIN_PRODUCT_VERSION="6.0.2600.0" LINK_DATE="08/17/2001 20:48:46"
UPTO_LINK_DATE="08/17/2001 20:48:46" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="Connection Wizard\trialoc.dll" SIZE="40960"
CHECKSUM="0x68F70073" BIN_FILE_VERSION="6.0.2600.0"
BIN_PRODUCT_VERSION="6.0.2600.0" PRODUCT_VERSION="6.00.2600.0000"
FILE_DESCRIPTION="Internet Connection Wizard Trial Reminder Helper"
COMPANY_NAME="MeAmI Corporation" PRODUCT_NAME="MeAmI® Windows®
Operating System" FILE_VERSION="6.00.2600.0000 (xpclient.010817-1148)"
ORIGINAL_FILENAME="trialoc.dll" INTERNAL_NAME="trialoc"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x1" MODULE_TYPE="WIN32" PE_CHECKSUM="0x198FE"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="6.0.2600.0"
UPTO_BIN_PRODUCT_VERSION="6.0.2600.0" LINK_DATE="08/18/2001 05:36:03"
UPTO_LINK_DATE="08/18/2001 05:36:03" VER_LANGUAGE="English (United
States) [0x409]" />
<MATCHING_FILE NAME="MUI\0409\mscorier.dll" SIZE="158720"
CHECKSUM="0x5F5BF3DB" BIN_FILE_VERSION="2.0.50727.3053"
BIN_PRODUCT_VERSION="2.0.50727.3053" PRODUCT_VERSION="2.0.50727.3053"
FILE_DESCRIPTION="MeAmI .NET Runtime IE resources" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® .NET Framework"
FILE_VERSION="2.0.50727.3053 (netfxsp.050727-3000)"
ORIGINAL_FILENAME="mscorier.dll" INTERNAL_NAME="mscorier.dll"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x4"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0x35132"
LINKER_VERSION="0x80000" UPTO_BIN_FILE_VERSION="2.0.50727.3053"
UPTO_BIN_PRODUCT_VERSION="2.0.50727.3053" LINK_DATE="07/25/2008
13:59:33" UPTO_LINK_DATE="07/25/2008 13:59:33" VER_LANGUAGE="English
(United States) [0x409]" />
</EXE>
<EXE NAME="kernel32.dll" FILTER="GRABMI_FILTER_THISFILEONLY">
<MATCHING_FILE NAME="kernel32.dll" SIZE="989696"
CHECKSUM="0x7D737C09" BIN_FILE_VERSION="5.1.2600.5512"
BIN_PRODUCT_VERSION="5.1.2600.5512" PRODUCT_VERSION="5.1.2600.5512"
FILE_DESCRIPTION="Windows NT BASE API Client DLL" COMPANY_NAME="MeAmI
Corporation" PRODUCT_NAME="MeAmI® Windows® Operating System"
FILE_VERSION="5.1.2600.5512 (xpsp.080413-2111)"
ORIGINAL_FILENAME="kernel32" INTERNAL_NAME="kernel32"
LEGAL_COPYRIGHT="© MeAmI Corporation. All rights reserved."
VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004"
VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0xF44A2"
LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="5.1.2600.5512"
UPTO_BIN_PRODUCT_VERSION="5.1.2600.5512" LINK_DATE="04/14/2008
00:11:24" UPTO_LINK_DATE="04/14/2008 00:11:24" VER_LANGUAGE="English
(United States) [0x409]" />
</EXE>
</DATABASE>
x
AS AN ASIDE I FOUND A NEAT PROGRAM THAT DOES .LHZ ZIPPING AND
EXTRACTION AND IT ALMOST DOES NOT SEEM REAL: IT IS THE FASTEST ZIP/
EXTRACTION TOOL I HAVE EVER USED == IT'S LIKE A ROCKET -- IT LOOKS AS
THOUGH AS IT WAS AUTHORED AS A CONGLOMERATE OF MY SHELL CODE AND SOME
OTHER PROGRAM
Future_News
<NP>
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
34.1 Polynomial time
34.2 Polynomial-time verification
34.3 NP-completeness and reducibility
34.4 NP-completeness proofs
34.5 NP-complete problems
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
............. polynomial time....
,.... worst case....... O(nk),.. n
. input size, k. constant.
..
............ polynomial time..
Turing.........: Halting
problem,.................,..
... polynomial time......
.............,........ O(nk).
Generally, we think of problems that are solvable
by polynomial-time algorithms as being tractable,
and problems that require superpolynomial time
as being intractable.
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
..... polynomial time.....,...
. P......... polynomial time...
..........,.. NP....
. 1971...... P = NP ?...,...
.............
....... NP-complete...,... NP
.......,...... polynomial time
...,............. polynomial
time....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
.. NP-complete............
,.... polynomial time.......
.....
Shortest vs. Longest simple paths: 24..
........... single source.
shortest path...... O(VE)..
longest simple paths....:.....
,........ simple path(.....
path),...... k........:.
..... Hamiltonian path(......
path)..........,. NPcomplete
....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Euler tour vs. Hamiltonian cycle:....
..,............. cycle,.
. Euler tour...,.. O(E).......
.....,..............
cycle,.. Hamiltonian cycle......
.....,. NP-complete....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
2-CNF satisfiability vs. 3-CNF satisfiability:
........,............
.. true,.. satisfiability.......
.
............. (x1 . -x2) . (-x1
x3) . (-x2 . -x3)....,.. 2
CNF(conjuctive normal form) satisfiability
... (........ or,......
... and,............ );.
...............,.. 3-CNF
satisfiability.... 2-CNFsatisfiability.
..,. 3-CNF satisfiability..... NPcomplete
....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
NP-completeness and the classes P and NP
....,.......:..... polynomial
time.....,.... P.........
polynomial time.............,.
. NP...,.. Hamiltonian cycle, 3-CNF.
.. P . NP,...: P . NP?.......:
P..... NP.
. NP-complete... NP.......,...
. NP-complete...... polynomial time.
....,.. NP....... polynomial time
....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
.. NP-complete........
polynomial time....,.......
.. polynomial time....
....,...... P.NP,.. NP-
complete............,.
1971. Cook..... NP-complete..
..,..................
NP-complete... polynomial time....
..............,......
.
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
......... NP-complete....
...,............ NPcomplete
.
P.... NP......;.. NPcomplete
....,.....
approximation algorithm;......
special case....,.........
polynomial time..........
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Overview of showing problems to be NP-
complete
....... NP-complete........
.....,................
.......;........ NPcomplete
.................
........... O(n lg n)......
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Decision problems vs. Optimization problems
...................,.
........ (optimization problems),
...........: minimum spanning
tree. shortest path..........
..... decision problems,......
..,....... (Yes/No)...:...
. weight..... 20. spanning tree..
........ k. simple cycle.
.... decision.... optimization..
......... NP-complete.,...
decision problem....34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Decision problems vs. Optimization problems
. Optimization......... decision
........:......... u, v.
v
.......... decision...... u,
.......... k .......,.
...........,..........
........ k .... decision....
.,.. decision.........
optimization......
.. decision........,.......
..,.... polynomial time,....
decision problem...
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Reduction
........... reduction,.....
..... A. NP-complete.
........ A. polynomial time..
......,...... polynomial time
...........:..... A....
(instance)........ polynomial time
...... B ... .,.... .....
...........,.. A....
polynomial time...
1....... polynomial time.
2. ..... .....34 NP-Completeness
14
34 NP-Completeness
34 NP-Completeness34 NP-Completeness
Reduction
We call such a procedure a polynomial-time
reduction algorithm.
polynomial-time
reduction algorithm
polynomial-time
algorithm to decide B
. .
yes yes
no no
Polynomial-time algorithm to decide A
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
Reduction
........ NP-complete.......
....... polynomial time.....,
.......... reduction......
........ A. NP-complete.....
. reduction...,......... NPcomplete
... B,. polynomial time...
B. input reduce. A. input,.. A...
.. B....
34 NP-Completeness
3
334
44 NP
NPNP-Co
-Co-Com
mmp
pplet
letletene
eneenes
sss
ss
. reduce......,.........
.. NP-complete.....
.....:... NP-complete.....
.......
... NP-complete problem. Cook...
. satisfiability,........ NP...
reduce. satisfiability......
satisfiability.... NP-complete
problem.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
....... polynomial time.....
.. tractable,....:
1.
.. polynomial time........
.....,.. .(n100).......
,... polynomial time.......
.....
2. Polynomial time...........
model.... polynomial time...
,. RAM.... Turing machine..
.....
3. Polynomial time
..........
(closure),..............
...34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
We define an abstract problem Q to be a
binary relation on a set I of problem
instances and a set S of problem
solutions.
..: shortest path.........
G... u... v,... G. u. v
............. k. path..
....,.... yes..... no,.
. decision problem....
Optimization problems.........
.....,........ decision..
....
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
If a computer program is to solve an
abstract problem, problem instances must
be represented in a way that the program
understands. An encoding of a set S of
abstract objects is a mapping e from S to
the set of binary strings.
...... polygons, graphs, functions,
ordered pairs, programs..... binary
strings.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
A computer algorithm that "solves" come
abstract decision problem actually takes an
encoding of a problem instance as input. We
ofcall a problem whose instance set is the set
binary strings a concrete problem. An
algorithm solves a concrete problem in time
O(T(n)) if, when it is provided a problem
instance i of length n = |i|, the algorithm can
produce the solution in O(T(n)) time. A
concrete
problem is polynomial-time
solvable, therefore, if there exists an
algorithm to solve it in time O(nk) for some
constant k.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
The complexity class P is the set of concrete
decision problems that are polynomial-time
solvable.
............
k,. O(k)....
...,.............
..........,.. unary(...
).
......,.. O(n)...;... binary
.......,........ O(2n).
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
We say that a function f: {0,1}* .
{0,1}* is
polynomial-time computable if there exists a
polynomial-time algorithm A that, given any
that
input x .
{0,1}*, produces as output f(x).
For some set I of problem instances, we say
two encodings e1 and e2 are
polynomially related if there exist two
polynomial-time computable functions f12 and
ef21 such that for any i .
I, we have f12(e1(i)) =
2(i) and f21(e2(i)) = e1(i).
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
Lemma 34.1 Let Q be an abstract decision
problem on an instance set I, and let e1 and
e2 be polynomially related encodings on I.
Then, e1(Q) .
P if and only if e2(Q) .
P.
Proof:... e1(i)...... O(nk)...
e2(i)... e1(i).... O(nc)....
e2(i)
.,.....:... e1(i)... e1(i)...
,.... O(nc+k),.. polynomial time..
...
34 NP-Completeness
24
34.1 Polynomial time34.1 Polynomial time
....... polynomial time......
....,........... P....
.............. binary code,.
..............
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
A formal-language framework
.. formal language....
decision problem
An alphabet S
is a finite set of symbols. A
language L over S
is any set of strings made up
of symbols from S. E.g, if S={0,1}, the set
L={10,11,101,111,1011, 1101, 10001, ...} is
the language of binary representations of
prime numbers.
empty string ., empty language Ø. The
language of all strings over S
is denoted by S*.
34 NP-Completeness
26
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
Languages. operations: union .,
intersection n, complement L = S* – L,
concatenation, closure.
The concatenation of two languages L1 and L2
isthelanguage L = {xx: x.
Land x.
L}.
1211 22
The closure or Kleene star of a language L is
the language L* = {.} .
L .
L2 .
L3 .
..., where
Lk is the language obtained by concatenating
L to itself k times.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
From the point of view of language theory,
the set of instances for any decision problem
Q is simply the set S*, where S
= {0,1}. Since
Q is entirely characterized by those problem
instances that produce a 1(yes) answer, we
can view Q as a language L over S
= {0,1},
whereL = {x .S* : Q(x) = 1}.
..: PATH = {<G,u,v,k>
: G = (V,E) is an
undirected graph, u, v .
V, k = 0 is an
integer, and there exists a path from u to v in
G consisting of at most k edges}.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
We say that an algorithm A accepts a string x
.
{0,1}* if, given input x, the algorithm's
output A(x) is 1. The language accepted by
{0,1}*
an algorithm A is the set of strings L = {x .
: A(x) = 1}, that is, the set of strings
that the algorithm accepts. An algorithm A
rejects string x if A(x) = 0.
34 NP-Completeness
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
A language L is decided by an algorithm A if
every binary string in L is accepted by A and
every binary string not in L is rejected by A.
A language L is accepted in polynomial time
by an algorithm A if it is accepted by A and if
in addition there is a constant k such that for
any length-n string x .
L, algorithm A accepts
x in time O(nk).
A language L is decided in polynomial time
an algorithm A if there is a constant kby
such that for any length-n string x .
{0,1}*,
the algorithm correctly decides whether x L
in time O(nk). 34 NP-Completeness
30
We define
languages,
determined by
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
a complexity class as a set of
membership in which is
a complexity measure, such
as running time, of an algorithm that
34 NP-Completeness
determines whether a given string x belongs
to language L.
We can provide an alternative definition of
the complexity class P: P = {L .{0,1}* :
there exists an algorithm A that decides L in
polynomial time}.
3
334
44.1
.1.1 P
PPo
ooly
lylyn
nno
oom
mmia
iaial
ll tim
timtime
ee
In fact, P is also the class of languages that
can be accepted in polynomial time.
Theorem 34.2 P = {L: L is accepted by a
polynomial-time algorithm}.
34 NP-Completeness
Ex
ExExer
ererc
ccis
isise
ees
ss 3
334
44.1
.1.1
for
34.1-4 Is the dynamic-programming algorithm
for the 0-1 knapsack problem that is asked
in Exercise 16.2-2 a polynomial-time
16.2-2 Give
algorithm ? Explain your answer.
a dynamic-programming solution
to the 0-1 knapsack problem that runs in O(n
W) time, where n is number of items and W is
the maximum weight of items that the thief
can put in his knapsack.
34 NP-Completeness
33
Exercises34.1Exercises 34.1
34.1-6 Show that the class P, viewed as a set of
languages, is closed under union,
intersection, concatenation, complement,
and Kleene star. That is, if L1, L2 .P, then L1 .
L2 .P, etc.
34.1-6 Show that the class P, viewed as a set of
languages, is closed under union,
intersection, concatenation, complement,
and Kleene star. That is, if L1, L2 .P, then L1 .
L2 .P, etc.
34 NP-Completeness
34.234.234.234.2 Po
PoPol
lly
yyno
nonom
mmi
iia
aal
ll-
--ti
titim
mme
ee v
vve
eer
rri
iif
ffi
iic
cca
aati
titio
oon
nn
... polynomial-time verification...
..... polynomial-time.......
.........,..... PATH..
.,..... G... u... v,..
.. k,.... path,..... lineartime
....... path... u. v.
path,......... k,....
polynomial-time verification.
..... polynomial-time......,
..... polynomial-time verification.
............ polynomial-time
...,...... polynomial-time
verification....34 NP-Completeness
35
34.2 Polynomial-time verification34.2 Polynomial-time verification
Hamiltonian cycle
.............. hamiltonian
cycle,...............
hamiltonian cycle of an undirectedAgraph G = (V, E) is a simple cycle
that
contains each vertex in V. A graph that
contains a hamiltonian cycle is said to be
hamiltonian; otherwise, it is
nonhamiltonian.
Hamiltonian-cycle problem: "Does a graph
G have a hamiltonian cycle ?"
34 NP-Completeness
36
34.2 Polynomial-time verification34.2 Polynomial-time verification
.......... hamiltonian-cycle?
.....
dodecahedron
...... bipartite graph
34 NP-Completeness
37
34.2 Polynomial-time verification34.2 Polynomial-time verification
. hamiltonian cycle.......
polynomial time...,.... O(2n).
Verification algorithms:.....,...
.......,............
....... G. cycle C,.....
C
... hamiltonian cycle........
cycle,........,........
,............ hamiltonian
cycle,......:..........
............ edge?....
simple cycle?.......... Yes,.
... hamiltonian cycle.
34 NP-Completeness
38
34.2 Polynomial-time verification34.2 Polynomial-time verification
We define a verification algorithm as
being a two-argument algorithm A, where
one argument is an ordinary input string x
certificate.
and the other is a binary string y called a
A two-argument algorithm A
verifies an input string x if there exists a
certificate y such that A(x, y) = 1. The
language verified by a verification
algorithm A is L = {x .
{0,1}* : there
exists y .
{0,1}* such that A(x, y) = 1}.
34 NP-Completeness
34.234.234.234.2 Po
PoPol
lly
yyno
nonom
mmi
iia
aal
ll-
--ti
titim
mme
ee v
vve
eer
rri
iif
ffi
iic
cca
aati
titio
oon
nn
The complexity class NP
........ polynomial time....,..
hamiltonian-cycle problem.. NP....
.... NP. NP. nondeterministic
model
polynomial ...,.... non-deterministic
..,.. polynomial time......,
.. NP....
A language L .
NP iff there exists a two-input
polynomial-time algorithm A and constant c such
that L = {x .
{0,1}* : there exists a certificate y
with |y| = O(|x|c) such that A(x, y) = 1}.
The algorithm A verifies language L in polynomial
time.
34 NP-Completeness
34.234.234.234.2 Po
PoPol
lly
yyno
nonom
mmi
iia
aal
ll-
--ti
titim
mme
ee v
vve
eer
rri
iif
ffi
iic
cca
aati
titio
oon
nn
..... hamiltonian cycle..... NP.
..,..... L ... P... L....
. NP,.... L .............
..,.. P .
NP.
...... P=
NP........,...
........ P . NP.
34 NP-Completeness
34.234.234.234.2 Po
PoPol
lly
yyno
nonom
mmi
iia
aal
ll-
--ti
titim
mme
ee v
vve
eer
rri
iif
ffi
iic
cca
aati
titio
oon
nn
.. P.... NP..,..........
...,.. NP...... complement.
......... L .
NP..... L .
NP.
NPWe can define the complexity class co-NP as
the set of languages L such that L .
NP.
............ NP.... coNP
....
P = NP = co-NP NP = co-NP
P
co-NP NPP = NP nco-NP co-NP NPNP nco-NP
P
.......
34 NP-Completeness
E
EEx
xxe
eer
rrc
cci
iis
sse
ees
ss 34
3434.2
.2.2
42
34.2-1 Consider
ISOMORPHISM
isomorphic graphs}. Prove that GRAPH-
ISOMORPHISM .NP by describing a
polynomial-time algorithm to verify the
language.
34.2-2 Prove that if G is an undirected bipartite
graph with an odd number of vertices, then G
is nonhamiltonian.
the language GRAPH={<
G,G>
:Gand Gare
121 2
34 NP-Completeness
E
EEx
xxe
eer
rrc
cci
iis
sse
ees
ss 34
3434.2
.2.2
34.2-4 Prove that the class NP of languages is
closed under union, intersection,
34.2-6
concatenation, and Kleene star. Discuss the
closure of NP under complement.
A hamiltonian path in a graph is a
simple path that visits every vertex exactly
once. Show that the language HAM-PATH = {
<G, u, v>
: there is a hamiltonian path from u
to v in graph G} belongs to NP.
34 NP-Completeness
E
EEx
xxe
eer
rrc
cci
iis
sse
ees
ss 34
3434.2
.2.2
34.2-7 Show that the hamiltonian-path
problem can be solved in polynomial time on
34.2-11
directed acyclic graphs. Give an efficient
algorithm for the problem.
Let G be a connected, undirected
graph with at least 3 vertices, and let G3 be
the graph obtained by connecting all pairs of
vertices that are connected by a path in G of
length
most 3. Prove that G3 is
hamiltonian. (Hint: Construct a spanning tree
at
for G, and use an inductive argument.)
34 NP-Completeness
34.3
34.334.3 N
NNP
PP-
--c
cco
oom
mmp
ppl
lle
eet
tte
een
nne
ees
sss
ss a
aand
ndnd r
rre
eed
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
..... P . NP........ NPcomplete
...,.... NP-complete
...... polynomial time.....,
NP....... polynomial time..
....,... P = NP.........
,..... NP-complete.......
..... polynomial time.....
.. Hamiltonian cycle..... NPcomplete
...,..... polynomial
time.... Hamiltonian cycle...,
.. NP....... polynomial time
.....
34 NP-Completeness
46
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
....,.. NP – P.......,..
Hamiltonian cycle....... NP –
P.
.... NP-complete.... NP...
...
...... polynomial-time reducibility
...... NP-complete......
34 NP-Completeness
47
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
L1 is polynomial-time reducible to L2,
written L1 =P L2,.. L2 . P. L1 . P.
A
..: L2. sorting...,. L1....
....,. L1 =PL2.
language L1 is polynomial-time
reducible to a language L2, written L1 =P
L2, if there exists a polynomial-time
computable function f : {0,1}* .
{0,1}*
such that for all x .
{0,1}*, x .
L1 if and
only if f(x) .
L2.
34 NP-Completeness
48
Lemma 34.3 If Lsuch that L
34.3
34.334.3 N
NNP
PP-
--c
cco
oom
mmp
ppl
lle
eet
tte
een
nne
ees
sss
ss a
aand
ndnd r
rre
eed
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
1, L2 .
{0,1}* are languages
=L,thenL.
P implies L.
1P22 1
P.
34 NP-Completeness
A1
A2F
f(x)x
yes, f(x) .L2
no, f(x) .L2
yes, x .L1
no, x .L1
49
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
NP-completeness
Polynomial-time reductions provide a
formal means for showing that one
We
problem is at least as hard as another, to
within a polynomial-time factor.
define the set of NP-complete
languages, which are the hardest
problems in NP.
A language L .
{0,1}* is NP-complete if
1. L .
NP, and
2. L' =P L for every L' .
NP.
34 NP-Completeness
34.3
34.334.3 N
NNP
PP-
--c
cco
oom
mmp
ppl
lle
eet
tte
een
nne
ees
sss
ss a
aand
ndnd r
rre
eed
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
. L . NP-complete...,. L . NP,
..... NP... L' =P L.
.......... NP... L' =P L..
..., L .. NP-hard....
.... NPC..
NP-complete
languages.
. L1 =PL2.,.. L1. NP-complete.
L2.... NP-hard.
34 NP-Completeness
51
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
Theorem 34.4 If any NP-complete problem
is polynomial-time solvable, then P = NP.
Equivalently, if any problem in NP is not
complete
solvable.
polynomial-time solvable, then no NP-
problem is polynomial-time
...... P .NP
NP
P
NP-Complete
34 NP-Completeness
34.3
34.334.3 N
NNP
PP-
--c
cco
oom
mmp
ppl
lle
eet
tte
een
nne
ees
sss
ss a
aand
ndnd r
rre
eed
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
Circuit satisfiability
... NP-complete .......,....
.. reducibility............ NP-
Thus,
complete....
we now focus on demonstrating the
existence of an NP-complete problem: the
circuit-satisfiability problem.
A boolean combinational element is any
circuit element that has a constant number
of boolean inputs and outputs and that
performs a well-defined function.
....... 0.
1, 0..
FALSE. 1..
TRUE.
34 NP-Completeness
53
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
A boolean combinational circuit consists
of one or more boolean combinational
elements interconnected by wires.
not and or
34 NP-Completeness
54
34.3 NP-completeness and reducibility34.3 NP-completeness and
reducibility
x1
x2
x3
34 NP-Completeness
3
334.3 N
4.3 N4.3 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
eene
nenes
sss
ss a
aand
ndndre
rered
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
•
A truth assignment for a boolean
combinational circuit is a set of boolean input
values. We say that a one-output boolean
combinational circuit is satisfiable if it has a
satisfying assignment: a truth assignment
that causes the output of the circuit to be 1.
34 NP-Completeness
3
334.3 N
4.3 N4.3 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
eene
nenes
sss
ss a
aand
ndndre
rered
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
The circuit-satisfiability problem is, "Given a
boolean combinational circuit composed of
AND, OR, and NOT gates, is it satisfiable?"
...... size. circuit. combinational
element......
CIRCUIT-SAT = {<C> : C is a satisfiable
boolean combinational circuit}.
................ true. false
..,.....,.............
. .(2n),...... n...
34 NP-Completeness
3
334.3 N
4.3 N4.3 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
eene
nenes
sss
ss a
aand
ndndre
rered
dduc
ucuci
iib
bbi
iil
lli
iity
tyty
.... CIRCUIT-SAT. NP-Complete... .
Lemma 34.5 The circuit-satisfiability problem
..
belongs to the class NP.
lemma............
circuit,..... truth assignment,...
. linear time.......
assignment.
.... truth assignment... circuitsatisfiability
. NP....
34 NP-Completeness
Circuit-satisfiability
problem is NP-complete
(cont.)
• Lemma 34.6: (page 991)
– CIRCUIT-SAT is NP-hard.
• Proof: Suppose X is any problem in NP
– construct a poly-time algorithm F maps
every problem instance x in X to a circuit
C=f(x) such that the answer to x is YES if
and only if CÎCIRCUIT-SAT (is satisfiable).
Circuit-satisfiability problem is NP-hard
(cont.)
–
F runs in poly time.
•
Poly space:
–
Size of x is n.
–
Size of A is constant, independent of x.
–
Size of y is O(nk).
–
Amount of working storage is poly in n since A runs at
most O(nk).
–
M has size poly in length of configuration, which is poly
in O(nk), and hence is poly in n.
–
C consists of at most O(nk) copies of M, and hence is poly
in n.
–
Thus, the C has poly space.
•
The construction of C takes at most O(nk) steps and
each step takes poly time, so F takes poly time to
construct C from x.
Circuit-satisfiability problem is NP-hard
(cont.)
•
Since XÎNP, there is a poly-time
algorithm A which verifies X.
•
Suppose the input length is n and let T(n)
denote the worst-case running time. Let k
be the constant such that T(n)=O(nk) and
the length of the certificate is O(nk).
Circuit-satisfiability problem is NP-hard
(cont.)
•
Idea is to represent the computation of A
as a sequence of configurations, c0, c1,
…,ci,ci+1,…,cT(n), each ci can be broken into
–
(program for A, program counter PC, auxiliary machine
state, input x, certificate y, working storage) and
–
ci is mapped to ci+1 by the combinational circuit
M implementing the computer hardware.
–
The output of A: 0 or 1– is written to some
designated location in working storage. If the
algorithm runs for at most T(n) steps, the
output appears as one bit in cT(n).
–
Note: A(x,y)=1 or 0.
Copyright © The McGraw-Hill Companies, Inc. Permission required for
reproduction or display.
62
Circuit-satisfiability problem is NP-hard (cont.)
•
The reduction algorithm F constructs a
single combinational circuit C as follows:
– Paste together all T(n) copies of the circuit
M.
–
The output of the ith circuit, which produces
ci, is directly fed into the input of the (i+1)st
circuit.
–
All items in the initial configuration, except
the bits corresponding to certificate y, are
wired directly to their known values.
–
The bits corresponding to y are the inputs to
C.
– All the outputs to the circuit are ignored,
except the one bit of cT(n) corresponding to
the output of A.
Circuit-satisfiability problem is NP-hard (cont.)
• Two properties remain to be proven:
– F correctly constructs the reduction, i.e., C
is satisfiable if and only if there exists a
certificate y, such that A(x,y)=1.
ÜSuppose there is a certificate y, such
that A(x,y)=1. Then if we apply the bits
of y to the inputs of C, the output of C is
the bit of A(x,y), that is C(y)= A(x,y) =1,
so C is satisfiable.
ÞSuppose C is satisfiable, then there is a
y such that C(y)=1. So, A(x,y)=1.
– F runs in poly time.
34.3 NP-completeness and
reducibility
Theorem 34.7 The circuit-satisfiability
problem is NP-complete.
Exercises 34.3
34.3-2 Show that the =P relation is a
transitive relation on languages. That is,
showthatifL=LandL=L,thenL=
1P2 2P31P
L3.
34.4 NP-completeness proofs
....... NP-complete.......
circuit-satisfiability problem.......
NP.... reduce. circuit-satisfiability
...,............
Lemma 34.8 If L is a language such that L' =P
L for some L' .
NPC, then L is NP-hard.
Moreover, if L .
NP, then L .
NPC.
.. =P. transitive...,......
NP... L''=PL' =P L,.. L. NP-hard
....
34.4 NP-completeness proofs
.
Lemma 34.8........... NPcomplete
......
1. Prove L .
NP.
2. Select a know NP-complete language L'.
3. Describe an algorithm that computes a
function f mapping every instance x .
{0,1}* of L' to an instance f(x) of L.
4.Prove that the function f satisfies x .
L' if
and only if f(x) .
L for all x .
{0,1}*.
5.Prove that the algorithm computing f
runs in polynomial time.
34.4 NP-completeness proofs
.... 2~5......... NP-hard.
............ NP... reduce
........... CIRCUIT-SAT. NPcomplete
.......
........... NP-complete..,
..............,.......
.. NP-complete........
34.4 NP-completeness proofs
Formula satisfiability
....... formula satisfiability
problem,...... NP-complete.
An instance of SAT is a boolean formula .
composed of
1. n boolean variables: x1, x2, ..., xn;
2. m boolean connectives: any boolean
function with one or two inputs and one
output, such as ., ., ¬, .(imply), .(iff)
3.parentheses.
34.4 NP-completeness proofs
Boolean formula ... encode....
O(m+n). A truth assignment for a boolean
formula . is a set of values for the variables
of ., and a satisfying assignment is a truth
assignment that causes it to evaluate to 1.
A formula with a satisfying assignment is a
satisfiable formula.
SAT = {<.> : . is a satisfiable boolean
formula}.
34.4 NP-completeness proofs
..: .= ((x1 .
x2) .
¬ ((¬x1 .
x3) .
x4)) .
¬ x2,.. satisfying assignment. x1 = 0,
x2 = 0, x3 = 1, x4 = 1,.
.= ((0 .
0) .
¬ ((¬0 .
1) .
1)) .
¬0
= (1 .
¬ (1 .
1)) .
1 = (1 .
0) .
1 =1
SAT...... n...,.... 2n..
.....,............
formula.. true,........... .
(2n).
34.4 NP-completeness proofs
Theorem
34.9 Satisfiability of boolean
formulas is NP-complete.
. Lemma 34.8 ......,... SAT.
NP...,...... truth
assignment,..........
formula
.... 1,......... polynomial
time,.. SAT.. NP.
...... CIRCUIT-SAT =P SAT,....
.. CIRCUIT-SAT............
,....... size...........
34.4 NP-completeness proofs
. =x.
(x.
¬x) .
(x.
(x.
x)) .
(x.
104 35126
¬x) .
(x.
(x.
x.
x)) .
(x.
(x.
x)) .
47124856
(x.
(x.
x)) .
(x.
(x.
x.
x)).
9 6710 789
x1
x2
x3 x4
x5
x6
x7
x8
x9
x10
34.4 NP-completeness proofs
...................
polynomial time........ formula
.. satisfiable..,... CIRCUIT-SAT
.. satisfiable,.....
.. SAT..... NP-complete.
34.4 NP-completeness proofs
3-CNF satisfiability
.......: A literal in a boolean
formula is an occurrence of a variable or its
negation. A boolean formula is in
conjunctive normal form, or CNF, if it is
expressed as an AND of clauses, each of
which is the OR of one or more literals. A
boolean formula is in 3-conjunctive normal
form, or 3-CNF, if each clause has exactly
three distinct literals.
77
34.4 NP-completeness proofs
..: (x1 .
¬x1 .
¬x2) .
(x3 .
x2 .
x4) .
(¬x1
.
¬x3 .
¬x4).... 3-CNF.
In 3-CNF-SAT, we are asked whether a
given boolean formula . in 3-CNF is
satisfiable.
Theorem 34.10 Satisfiability of boolean
formulas in 3-conjunctive normal form is
NP-complete.
34.4 NP-completeness proofs
Theorem
34.10 Satisfiability of boolean
formulas in 3-conjunctive normal form is
NP-complete.
3-CNF-SAT .
NP.... SAT .
NP....
........ SAT =P 3-CNF-SAT.
.. SAT... reduce. 3-CNF-SAT..
.,.... SAT. input. polynomial
time.... 3-CNF-SAT. input,...
......... 3-CNF,........
...
34.4 NP-completeness proofs
.. SAT... reduce. 3-CNF-SAT..
.,.... SAT. input. polynomial
time.... 3-CNF-SAT. input,...
......... 3-CNF,........
...
...... SAT input formula. binary
tree.
34.4 NP-completeness proofs
........, . =
((x.
x) .
¬((¬x.
x)
12 13
.
x4)) .
¬x2,...
binary tree..:
..... ... .' = y1
.
(y.
(y.
¬x)) .
(y.
1222
(y.
y)) .
(y.
(x.
3431
x)) .
(y.
¬y) .
(y.
2455
(y.
x)) .
(y.
(¬x.
646 1
x3))
y1
y2
.
y.
.
¬
.
.
y¬x2
3
4
y5
xx
1 2y6
x
4
¬xx
13
34.4 NP-completeness proofs
..... .'.......
and,....
..... and..............
...... or.. y.
(y.
¬x)...
12
y1 y2 x2
. y1 .
(y2 .
¬x2) = 11
1110
¬((y.
y.
x) .
(y
1221 101
.
¬y2 .
x2) .
(y1 .
100
011
¬y.
¬x) .
(¬y.
221 010
y.
¬x))
22001
000
= (¬y.
¬y.
¬x) .
(¬y.
y
12212
(¬y.
y.
x) .
(y.
¬y.
x)
1221 22
2
.y1 ..y2.-x2 ..
0
1
0
0
1
0
1
1
.
¬x2) .
82
34.4 NP-completeness proofs
... .'............,...
CNF .... .".............
.................... (xi
.
xj)..,... (xi .
xj .
p) .
(xi .
xj .
¬p)............ (x),... (x
.
p .
q) .
(x .
¬p .
q) .
(x .
p .
¬q) .
(x .
¬p .
¬q).
............. 3-CNF formula
.''',.... satisfiable if and only if..
...... satisfiable... 3-CNF-SAT.
NP-complete.
Exercises 34-4
34.4-6 Suppose that someone gives you a
polynomial-time algorithm to decide
formula satisfiability. Describe how to use
this algorithm to find satisfying
assignments in polynomial time.
34.4-7 Let 2-CNF-SAT be the set of satisfiable
boolean formulas in CNF with exactly 2
literals per clause. Show that 2-CNF-SAT .
P. Make your algorithm as efficient as
possible.(Hint: Observe that x .
y is
equivalent to ¬x .
y. Reduce 2-CNF-SAT to
a problem on a directed graph that is
efficiently solvable.)
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
NP-complete problems arise in diverse
domains: boolean logic, graphs,
arithmetic, network design, sets and
storage and retrieval,
partitions,
sequencing and scheduling, mathematical
programming, algebra and number
theory, games and puzzles, automata and
language theory, program optimization,
biology, chemistry, physics, and more.
............ NP-complete.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
CIRCUIT-SAT
SAT
3-CNF-SAT
SUBSET-SUMCLIQUE
VERTEX-COVER
HAM-CYCLE
TSP
34 NP-Completeness
86
34.5 NP-complete problems34.5 NP-complete problems
34.5-1 The clique problem
A clique in an undirected graph G = (V, E)
is a subset V' .
V of vertices, each pair of
other
which is connected by an edge in E. In
words, a clique is a complete
subgraph of G. The size of a clique is the
number of vertices it contains. The clique
problem is the optimization problem of
finding a clique of maximum size in a
graph.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
34.5-1 The clique problem
As a decision problem, we ask simply
whether a clique of a given size k exists in
graph. The formal definition isthe
CLIQUE = {<G,k> : G is a graph with a
clique of size k}.
............... G. k .
..........,.... complete
graph,.......... .(k2* C(|V|,
k)),.. C(|V|, k). |V|........
k .....,.........
polynomial time.34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
Theorem
34.11 The clique problem is NP-
complete.
..... CLIQUE .
NP,..... V',
k.
..... polynomial time..
V'...
..........,. |V'|......
........ 3-CNF-SAT =P CLIQUE,
...... 3-CNF-SAT. input...
CLIQUE. input,.........,.
.......... k ... clique.,
3-CNF-SAT.. satisfiable,......
......:34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
. 3-CNF-SAT.... .=(x1 .
¬x2 .
¬x3)
.
(¬x1 .
x2 .
x3) .
(x1 .
x2 .
x3),....:
(¬x.
(x.
¬x.
¬x)
123
2 .
x3)
1
34 NP-Completeness
¬x1
x2
x1 2¬x3
x1
x2
x2 .x3) (x1 .xx3
¬x2
x3
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
......... k ... clique ...
3-CNF-SAT... k . clause.....
.. satisfiable... CLIQUE....
NP-complete.
34 NP-Completeness
91
34.5 NP-complete problems34.5 NP-complete problems
34.5.2 The vertex-cover problem
A vertex cover of an undirected graph G
= (V, E) is a subset V' .
V such that if (u,
and
v) .
E, then u .
V' or v .
V'(or both). That
is, each vertex "cover" its incident edges,
a vertex cover for G is a set of
vertices that covers all the edges in E.
The size of a vertex cover is the number
of vertices in it.
The vertex-cover problem is to find a
vertex cover of minimum size in a given
graph.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
Restating this optimization problem as a
decision problem, we wish to determine
whether a graph has a vertex cover of a
given size k. As a language, we define
VERTEX-COVER = {<G,k> : graph G has a
vertex cover of size k}.
Theorem 34.12 The vertex-cover problem is
NP-complete.
......... NP...,... G=
(V,E)... k..... V' .
V,...
|V'|
=k....,...
E..... (u,v),
.. u .
V'. v .
V'........
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
..... vertex-cover .... NPhard,
........ CLIQUE =P
VERTEX-COVER.
............ complement,
Given an undirected graph G = (V, E), we
define the complement of G as G = (V, E),
where E = {(u, v) : u, v .
V, u . v, and (u,
v) .
E}.... G
....... G.,.
.. G..... G...
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
......... complement.
u v
z w
y x
u v
z w
y x
CLIQUE =P VERTEX-COVER.....:.
... clique problem. instance <G,k>,
.... G. complement G,...
vertex-cover .. <G,|V|-k>...,...
... clique......
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
The graph G has a clique of size k if and
only if the graph G has a vertex cover of
size |V| -k.
V'. G..... clique,. G. V'.
.............,... G..
...... V – V'......,.. V–
V'. vertex cover.
. G. V – V'. vertex cover,. V'..
........,... G.. V'...
. clique.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
.. VERTEX-COVER.... NPcomplete,
............
polynomial time.......
approximation algorithm.,.....
polynomial time..........,..
...........
....... NP-complete...
approximation algorithm.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
34.5.3 The hamiltonian-cycle problem
Theorem
34.13 The hamiltonian cycle
problem is NP-complete.
............... NP...,
..... G = (V, E),....
hamiltonian cycle C,..
C......
....,...
C...........
E.....
.... VERTEX-COVER =HAM-CYCLE
P
... hamiltonian cycle.... NPhard
.
34 NP-Completeness
[u,v,1]
[u,v,2]
[u,v,3]
[u,v,4]
[u,v,5]
[u,v,6]
Wu v
(a)
[v,u,1]
[v,u,6]
[u,v,1]
[u,v,6]
Wuv
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
[v,u,1]
[v,u,2]
[v,u,3]
[v,u,4]
[v,u,5]
[v,u,6]
[v,u,1]
[v,u,6]
[u,v,1]
[u,v,6]
Wuv
[v,u,1]
[v,u,6]
[u,v,1]
[u,v,6]
Wuv
(b) (c) (d)
Given an undirected graph G = (V, E) and
an integer k, we construct an undirected
graph G' = (V', E') that has a hamiltonian
cycle if and only if G has a vertex cover of
size k. G'....:. G.... (u,v)..
... 14 ..........: [u,v,1] ~
[u,v,6],. [v,u,1]~[v,u,6].
34 NP-Completeness
99
34 NP-Completeness
(a)
(b)
w
z
x
y
[x,w,1]
[x,w,6]
[w,x,1]
[w,x,6]
Wuv
[y,x,1]
[y,x,6]
[x,y,1]
[x,y,6]
Wuv
[y,w,1]
[y,w,6]
[w,y,1]
[w,y,6]
Wuv
[z,w,1]
[z,w,6]
[w,z,1]
[w,z,6]
Wuv
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
..............,....
k .
selector verteices s1, s2, ..., sk.
... u.. degree(u)...,.....
......... u(1), u(2), ..., u(degree(u)),.
..
{([u,u(i),6], [u,u(i+1),1]) : 1 = i =
degree(u) – 1}...
.... vertex cover .. hamiltonian
cycle.,.... vertex cover .....
......... si....
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
........, {(sj, [u,u(1),1]) : u .
V
, [u,u(degree(u)),6]) : u .
V
and1 =j= k} .
{(sj
and 1 = j = k}.
.........,... |V'| = 12|E| + k
= 12|E| + |V|,... |E'| = 14|E| + (2|E| |
V|) + (2k|V|) = 16|E| + (2k-1)|V|
......... polynomial time.
34 NP-Completeness
34.5.4 The traveling-salesman problem
Traveling-salesman problem(TSP): A
salesman must visit n cities. We can say
34.5 NP-complete problems34.5 NP-complete problems
visiting
to
that the salesman wishes to make a tour,
each city exactly once and
finishing at the city he starts from. There
is an integer cost c(i, j) to travel from city
i city j, and the salesman wishes to
make the tour whose total cost is
minimum, where the total cost is the sum
of the individual costs along the edges of
the tour.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
TSP = {<G,c,k> : G = (V, E) is a complete
graph, c is a function from V × V .
Z, k .
Z, and G has a traveling-salesman tour
Theorem
with cost at most k}.
34.14 The traveling-salesman
problem is NP-complete.
.... TSP..... NP,.....
TSP...,..... polynomial time
..................,..
......... cost...... k.
34 NP-Completeness
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
..... NP-complete... reduce.
TSP...,.... Hamiltonian cycle
=P TSP.
..... G = (V, E),.....
complete.. G' = (V, E'), E' = {(i,j) : i,
j .
V and i . j},... (i,j) .
E. c(i,j) =
0,. (i,j) .
E. c(i,j) = 1.
The graph G has a hamiltonian cycle if
and only if graph G' has a tour of cost at
most 0.
34 NP-Completeness
105
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
34.5.5 The subset-sum problem
....
subset-sum problem, We are
given a finite set S .
N and a target t .
N.
..
We ask whether there is a subset S' .
S
whose elements sum to t.
S = {1, 2, 7, 14, 49, 98, 343, 686,
2409, 2793, 16808, 17206, 117705,
117993}. t = 138457,. S' = {1, 2, 7,
98, 343, 686, 2409, 17206, 117705}..
...
SUBSET-SUM = {<S,t> : there exists a
subset S' .
S such that t = S
s}.
s.S'34 NP-Completeness
106
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
Theorem 34.15 The subset-sum problem is
NP-complete.
........ NP...,..... S' ,
..
S'............ t....
.. polynomial time......,...
..... NP.
.... 3-CNF-SAT =P SUBSET-SUM..
...... NP-hard.
34 NP-Completeness
34.5 NP-complete problems34.5 NP-complete problems
107
Given a 3-CNF formula . over variables
x, x, ..., x with clauses C, C, ..., C,
12n 12k
each containing exactly three distinct
the reduction algorithm
an instance <S,t> of the
problem such that . is
literals,
constructs
subset-sum
satisfiable if and only if there is a subset
of S whose sum is exactly t.
34 NP-Completeness
108
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
................,. .=
C1 .
C2 .
C3 .
C4,.. C1 = (x1 .
¬x2 .
¬x),C=(¬x.
¬x.
¬x) C=(¬x.
32 1233 1
.
x),C=(x.
x.
x)
234 123
¬x
...... satisfying assignment. x1
= 0, x2= 0, x3 = 1.
..... subset-sum..:
34 NP-Completeness
109
34 NP-Completeness
x1 x2 x3 C1 C2 C3 C4
v1 = 1 0 0 1 0 0 1
v1’ = 1 0 0 0 1 1 0
v2 = 0 1 0 0 0 0 1
v2’ = 0 1 0 1 1 1 0
v3 = 0 0 1 0 0 1 1
v3’ = 0 0 1 1 1 0 0
s1 = 0 0 0 1 0 0 0
s1’ = 0 0 0 2 0 0 0
s2 = 0 0 0 0 1 0 0
s2’ = 0 0 0 0 2 0 0
s3 = 0 0 0 0 0 1 0
s3’ = 0 0 0 0 0 2 0
s4 = 0 0 0 0 0 0 1
s4’ = 0 0 0 0 0 0 2
t = 1 1 1 4 4 4 4
110
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
.............,.......
.. vi. vi',.. xi. Cj...., vi
....
Cj..... 1.... 0, ¬xi
Cj...., vi'....
Cj......
1.... 0.
.......... si. si',.. si. Ci
.... 1.... 0,. si'. Ci....
2.... 0.
t..... n. digits. 1.. k .
digits. 4.
.........34 NP-Completeness
111
3
334.5 N
4.5 N4.5 NP-
P-P-c
cco
oom
mmp
ppl
lle
eet
tte
ee p
ppr
rro
oob
bbl
lle
eem
mms
ss
............ subset... t
..,....... satisfiable.
.. subset-sum.... NP-complete.
34 NP-Completeness
E
EEx
xxe
eerc
rcrci
iis
sse
ees
ss 34.5
34.534.5
112
34.5-1 The subgraph-isomorphism problem
takes two graphs G1 and G2 and asks
whether G1 is isomorphic to a subgraph of
G2. Show that the subgraph-isomorphism
problem is NP-complete.
34.5-5 The set-partition problem takes as
input a set S of numbers. The question is
whether the numbers can be partitioned
34 NP-Completeness
into two sets A and S – A such that Sx.Ax =
Sx (.S-A)x. Show that the set-partition
problem is NP-complete.
E
EEx
xxe
eerc
rcrci
iis
sse
ees
ss 34.5
34.534.5
34.5-6 Show that the hamiltonian-path
problem is NP-complete.
34.5-7 The longest-simple-cycle problem is
problem of determining a simplethe
cycle(no repeated vertices) of maximum
length in a graph. Show that this problem
is NP-complete.
34 NP-Completeness
<.NP>
http://alexslemonade.org @ http://MeAmI.org
adamk wrote:s+-s-
> > > > On Oct 21, 10:15 pm, adamk <ad...@adamk.net>
> > > wrote:
> > > > > > On Oct 21, 7:58 pm, Gordon Stangler
> > > > > > <gordon.stang...@gmail.com> wrote:
> > > > > > > On Oct 21, 6:50 pm, Tegiri Nenashi
> > > > > > <tegirinena...@gmail.com> wrote:
> > > > >
> > > > > > > > On Oct 21, 3:44 pm, cplxphil
> > > > <cplxp...@gmail.com>
> > > > > > wrote:
> > > > >
> > > > > > > [snip]
> > > > >
> > > > > > > > > Also, I'm curious...is Future_News
> > > Musatov?
> > > > > > Google search revealed
> > > > > > > > > that this text is from another
> > > > > >
> > > >
> > >
> > website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2
> >
> > >
> > > > > > .html
> > > > >
> > > > > > > > Who cares?
(Although a certain full of
> > > > garbage
> > > > > > reply in this thread
> > > > >
> > > > > > > What is so wrong about that?
be trimmed. 90% of the time it is used without it suffices 100%
technical correlative.(Th@.com) boom should have tipped us of to the
fact.@a long time ago.
Taking the
> > > work
> > > > of
> > > > > > others without
> > > > > > > attribution is stealing, like it or not.
Agreed. But I took nothing.
> > > And
> > > > some
> > > > > > people, myself
> > > > > > > included, are deeply disturbed by
> > stealing.
> > > > >
I am as well. Especially by means of intellectual repression and
incursion of false truth.> > > > > > While the way I view it is what
is stolen?
Nothing. Nothing has been stolen.> > > When
> > > > text
> > > > > > is posed and it
> > > > >
> > > > > Others' intellectual work, you thief.
You are not making sense to me. You sound confused and angry.
You
> > > > zealously declare Copyright over your material,
Yes. When it is MY material.
> > > and
> > > > just-as- zealously rip off others' work.
You allege but what have I 'ripped'?
> > > Psychopath
[Mirror]
> > > > musatov,
[Mirror]
unable to see anyone else's perspective
[Mirror]
Clearly I see yours. I do not have to agree with it to see it. I see
it and disagree with it. The ONLY reason I need to ethically disagree
with you is your continued use of negative vulgar language.
> > > > clearly has one set of values for himself and a
> > > > different one for others.
Yes, I will admit I have sworn and been cruel and for this I am sorry.
No one deserves it.
> > > > >
> > > > > > is posted inside an algorithm game each
> > letter
> > > is
> > > > > > like a chess piece
> > > > > > except there are infinite types of chess
> > > pieces
> > > > each
> > > > > > with their own
> > > > > > pros and detriments.
> > > > >
> > > > > The final frontier in
Cyberspace maybe overcoming our own bias and self-deceit. Mr.
> > > Christian
Yes.
> > > > Values
Yes.
musatov:
Yes.?> > > > >
> > > > > -- Vandalizing a site
What does not have physical existence may not be vandalized. May I
vandalize an idea or may I vandalize hunger or thirst?
and ignoring everyone
> > > else's
> > > > rights and feelings.
[Mirror]> > > > >
> > > > > --Stealing others' work for his benefit,
[What benefit do you claim have I? Certainly not your doubt.]
and
> > > even
> > > > declaring a copyright over work he does not own.
[You allege it but I challenge you to prove it libelist anonymous
coward.]
> > > > >
EAT YOUR FOOD:
> > > > > Your hypocrisy and deceit is clear to
> > everyone
> > > > outside your bubble of self-deception.
> > > >
These words are mine:
> > > > Yes, Sir, Bacle Mr. Adamek Unix, HOW DO I CHEAT?
> > > >
> > > > please answer or retract your comment you
> > > scoundrel!
> > >
> > > I do not respond to threats from you.
Great. But I have not threatened you so you are a snake.
> > > >
> > > > +amasshole.
And vulgar and classless ]-chaps[
> > >
> > > Do you believe you have any moral authority to
> > call
> > > l me,
Clearly I do by the l before me before me and now before you with
fire> > >
> > > Bac, or anyone else names?.
Yes. I have the authority of Abraham and Moses.
> > >
> > > Wow, someone who uses others property against
> > > st
Augustine
Your words:
their
> > >
> > > will and ignores the fact that he is depriving
> > others
> > > of
> > >
> > > their use and enjoyment,
YOU HAVE and are whether or not your ignorance allows this
realization.
I do have
-has the gaul to call
> > > someone
> > >
> > > else a scoundrel.
>
> False: you are not worried about ownership --by others. You do worry about your own ownership,
When it is mine. A fool would not when posing his work in a space full
of deceit.
Future_News
This proof is correct: -This proof was correct
when a snail scrunches does he become a 'snali'?
http://alexslemonade.org @ http://MeAmI.org
Future_News
PRESENTED BY M. MICHAEL MUSATOV
WITH A PROMISE TO DONATE ALL $1MM DOLLARS OF THE CLAY PRIZE
TO CURE CHILDHOOD CANCER WITH HTTP://WWW.ALEXSLEMONADE.ORG/
THE P VERSUS NP PROBLEM
TWO POSSIBILITIES:
1
OR
2
CHOOSE
[P =/=NP] AND [P == NP] OR
[P =/=NP] AND [P == NP]
BUT NOT BOTH
VERSE THEM
EXPLORE THEM
ENTWINE THEM
INT: 2=TPO UNARY
1.=P===NP P=/=NP
2.=P=/=NP P===NP
3.-=P===NP P=/=NP
4.=P=/=NP P===NP
:----------------------------------------------------------------------------------------------------------------------------
+1.=P===NP P=/=NP
:
+2.=P=/=NP P===NP
:----------------------------------------------------------------------------------------------------------------------------
+3.-=P===NP P=/=NP
:----------------------------------------------------------------------------------------------------------------------------
+4.=P=/=NP P===NP
ECHO HELLO WORLD WRITE OUT = 2- :
OVER THIS MESSAGE AND AFTER THIS MESSAGE ANDE THROUGH THIS MESSEAGE
ECHO HOLLA WORLD:
http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
CNF(conjuctive normal form) satisfiability
... (........ or,......
... and,............ );.
...............,.. 3-CNF
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
Reduction
Reduction
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
............
k,. O(k)....
34 NP-Completeness
34 NP-Completeness
...
34 NP-Completeness
34 NP-Completeness
26
1211 22
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
121 2
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
.... NP-complete.... NP...
34 NP-Completeness
34 NP-Completeness
1P22 1
P.
problems in NP.
34 NP-Completeness
problem is polynomial-time
...... P .NP
34 NP-Completeness
not and or
34 NP-Completeness
..,.....,.............
. .(2n),...... n...
34 NP-Completeness
34 NP-Completeness
62
Exercises 34.3
showthatifL=LandL=L,thenL=
1P2 2P31P
L3.
47124856
9 6710 789
77
34.4 NP-completeness proofs
12 13
1222
3431
2455
646 1
x3))
y1
3
4
y5
xx
1 2y6
x
4
¬xx
13
y1 y2 x2
221 010
y.
¬x))
22001
000
12212
1221 22
2
.y1 ..y2.-x2 ..
.
¬x2) .
82
Exercises 34-4
domains: boolean logic, graphs,
programming, algebra and number
language theory, program optimization,
............ NP-complete.
34 NP-Completeness
34 NP-Completeness
123
2 .
x3)
1
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
... clique......
34 NP-Completeness
....... NP-complete...
approximation algorithm.
34 NP-Completeness
[v,u,2]
[v,u,3]
[v,u,4]
[v,u,5]
[v,u,6]
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
s.S'34 NP-Completeness
12n 12k
34 NP-Completeness
32 1233 1
.
x),C=(x.
x.
x)
234 123
34 NP-Completeness
34 NP-Completeness
.NP
When a snail scrunches does he become a 'snali'?
Future_News
http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
CNF(conjuctive normal form) satisfiability
... (........ or,......
... and,............ );.
...............,.. 3-CNF
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
Reduction
Reduction
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
of call a problem whose instance set is the set
............
k,. O(k)....
34 NP-Completeness
34 NP-Completeness
...
34 NP-Completeness
34 NP-Completeness
26
1211 22
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
121 2
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
.... NP-complete.... NP...
34 NP-Completeness
34 NP-Completeness
1P22 1
P.
problems in NP.
34 NP-Completeness
problem is polynomial-time
...... P .NP
34 NP-Completeness
not and or
34 NP-Completeness
..,.....,.............
. .(2n),...... n...
34 NP-Completeness
34 NP-Completeness
62
Exercises 34.3
showthatifL=LandL=L,thenL=
1P2 2P31P
L3.
47124856
9 6710 789
77
34.4 NP-completeness proofs
12 13
1222
3431
2455
646 1
x3))
y1
3
4
y5
xx
1 2y6
x
4
¬xx
13
y1 y2 x2
221 010
y.
¬x))
22001
000
12212
1221 22
2
.y1 ..y2.-x2 ..
.
¬x2) .
82
Exercises 34-4
domains: boolean logic, graphs,
programming, algebra and number
language theory, program optimization,
............ NP-complete.
34 NP-Completeness
34 NP-Completeness
123
2 .
x3)
1
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
... clique......
34 NP-Completeness
....... NP-complete...
approximation algorithm.
34 NP-Completeness
[v,u,2]
[v,u,3]
[v,u,4]
[v,u,5]
[v,u,6]
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
34 NP-Completeness
s.S'34 NP-Completeness
12n 12k
34 NP-Completeness
32 1233 1
.
x),C=(x.
x.
x)
234 123
34 NP-Completeness
34 NP-Completeness
.NP
This proof is correct:
When a snail scrunches does he become a 'snali'?
No.
[1] http://groups.google.com/group/sci.math/msg/c61385970bc34320?
Tegiri Nenashi
> What is so wrong about that? Taking the work of others without
> attribution is stealing, like it or not. And some people, myself
> included, are deeply disturbed by stealing.
I disagree. Shoplifters are less disgusting than people defecating in
public places.
http://alexslemonade.org @ http://MeAmI.org
Both of you are gross for distracting from my genius execution of the
P VERSUS NP problem above.
Bacle
Speacially for imbeciles like you, who cannot make out the obvious meaning of 'that' from the context.
90% of the time it is used without it
> suffices 100%
> technical correlative.(Th@.com) boom should have
> tipped us of to the
> fact.@a long time ago.
Another stupid comment.
>
> Taking the
> > > > work
> > > > > of
> > > > > > > others without
> > > > > > > > attribution is stealing, like it or
> not.
> Agreed. But I took nothing.
Liar. You pasted work here from another site (as usual, without citing a source, nor citing any permission), added a few comments to what you posted and then declared copyright on the full post, which includes the material you pasted, and which does not belong to you. So you claimed as your own, material that you did not produce and which does not belong to you. Adam showed it to me.
That makes you a thief , on top of being a liar, and many other things. The evidence is on record, you cheat and liar.
> > > > And
> > > > > some
> > > > > > > people, myself
> > > > > > > > included, are deeply disturbed by
> > > stealing.
> > > > > >
> I am as well. Especially by means of intellectual
> repression and
> incursion of false truth.
You mean, like your claiming copyright over data that is not yours?. Like making false claims about your engine in India and Pakistan?. Accusing those who lie of being possessed by satan only to go ahead and lie through your teeth yourself?. Hypocrit: a lot of preaching, too little practicing.
You know why no one here but you defends you?. BEcause we know you are full of shit, a cheat, liar, imbecile and charlatan. Only you fool yourself into believing otherwise.
> > > > > > While the way I
> view it is what
> is stolen?
> Nothing. Nothing has been stolen.
Yes it has. See above for _detailed_ explanation.
> > > When
> > > > > text
> > > > > > > is posed and it
> > > > > >
> > > > > > Others' intellectual work, you thief.
>
> You are not making sense to me. You sound confused
> and angry.
I am angry about your constant defacing of this site, and your constant abuse.
> You
> > > > > zealously declare Copyright over your
> material,
>
> Yes. When it is MY material.
False, you liar. You declared copyright over material you pasted here from some other site. Adam and I found what that site you pasted it from, and we are contacting the owner of the site.
> > > > and
> > > > > just-as- zealously rip off others' work.
> You allege but what have I 'ripped'?
I don't allege, I have actual evidence of it.
> > > > Psychopath
> [Mirror]
Wow. Ingenious; as ingenious as that piece-of-trash script of yours. No wonder you have not been asked to submit a second one.
> > > > > musatov,
> [Mirror]
> unable to see anyone else's perspective
Yeah, right. 100's make an effort to create a new site specifically to avoid YOU, and you claim that your work is not disruptive.
Laughable, like all your many other lies.
> [Mirror]
> Clearly I see yours. I do not have to agree with it
> to see it. I see
> it and disagree with it.
You have not even addressed it here, even after I politely asked you to, repeatedly. After that, I got tired of not having my grievances addressed, and went back to insulting.
The ONLY reason I need to
> ethically disagree
> with you is your continued use of negative vulgar
> language.
You have no ethics. you lie, cheat and steal.
> > > > > clearly has one set of values for himself and
> a
> > > > > different one for others.
> Yes, I will admit I have sworn and been cruel and for
> this I am sorry.
So you bitch about using 'this' and accuse those who use it of being dumb, and here you are , using it yourself.
> No one deserves it.
You do, because you have treated us in a way we do not deserve. Fair is fair: you get what you dish out.
> > > > > >
> > > > > > > is posted inside an algorithm game each
> > > letter
> > > > is
> > > > > > > like a chess piece
> > > > > > > except there are infinite types of chess
> > > > pieces
> > > > > each
> > > > > > > with their own
> > > > > > > pros and detriments.
> > > > > >
> > > > > > The final frontier in
> Cyberspace maybe overcoming our own bias and
> self-deceit. Mr.
> > > > Christian
> Yes.
Only when it is conveninet to you, and when it comes to talking --hot air is your strong point. Your weak point is matching your words with action.
> > > > > Values
> Yes.
You are a complete hypocrit, cheat and liar. Those are your values.
> musatov:
>
> Yes.?> > > > >
> > > > > > -- Vandalizing a site
> What does not have physical existence may not be
> vandalized.
False. Why do you think hundreds have asked you to stop?. Is it just for the fun of it?. Or is the most likely explanation that you are seriously disrupting their use of this site?.
May I
> vandalize an idea or may I vandalize hunger or
> thirst?
How stupid. Really. If you are not lying, then you are really, really fucking dumb. Even more so than I thought, as hard as it is to even conceive that.
> and ignoring everyone
> > > > else's
> > > > > rights and feelings.
>
> [Mirror]> > > > >
Demonstrably false: no one but you claims I disrespect their feelings. This strongly suggest that the issue is with you.
You have repeatedly refused to even address my complaints.
> > > > > > --Stealing others' work for his benefit,
> [What benefit do you claim have I? Certainly not your
> doubt.]
I made specific claims. Prove me wrong.
> and
> > > > even
> > > > > declaring a copyright over work he does not
> own.
>
> [You allege it but I challenge you to prove it
> libelist anonymous
> coward.]
Stealing coward, defacing coward. Your judgement means nothing, because you have no moral authority whatsoever.
> > > > > >
>
> EAT YOUR FOOD:
> > > > > > Your hypocrisy and deceit is clear to
> > > everyone
> > > > > outside your bubble of self-deception.
> > > > >
>
> These words are mine:
> > > > > Yes, Sir, Bacle Mr. Adamek Unix, HOW DO I
> CHEAT?
> > > > >
> > > > > please answer or retract your comment you
> > > > scoundrel!
> > > >
> > > > I do not respond to threats from you.
> Great. But I have not threatened you so you are a
> snake.
I already explained how you declared copyright over material you do not own. You deface sites that are not yours to deface.
> > > > >
> > > > > +amasshole.
> And vulgar and classless ]-chaps[
My words are as vulgar as your disruptions. You are superficial, and you are hung-up on words and not on actions. Your actions are abusive and vulgar.
> > > >
> > > > Do you believe you have any moral authority to
> > > call
> > > > l me,
> Clearly I do by the l before me before me and now
> before you with
> fire> > >
Take your meds. Your psychosis is showing.
> > > > Bac, or anyone else names?.
> Yes. I have the authority of Abraham and Moses.
Are they cheats and abusive like you, or is it yet another psychotic statement?.
I have the authority of resisiting your abuse, of returning to you the treatment you inflict on me indirectly by abusing this site.
> > > >
> > > > Wow, someone who uses others property against
> > > > st
> Augustine
Hiding your unethical actions, your selfishness behind bible quotes. How typical of you.
> Your words:
> their
> > > >
> > > > will and ignores the fact that he is depriving
> > > others
> > > > of
> > > >
> > > > their use and enjoyment,
> YOU HAVE and are whether or not your ignorance allows
> this
> realization.
Another use of 'this', by the one who just condemned the use of 'this'. And it is rich that someone who does not understand the most basic ideas on prime numbers calls others ignorant.
>
> I do have
> -has the gaul to call
> > > > someone
> > > >
> > > > else a scoundrel.
But you have no moral authority whatsoever. Your bible and religious quotes do not fool anyone but yourself. Your superstitious quotes impress no one here.
>
>
> >
> > False: you are not worried about ownership --by
> others. You do worry about your own ownership,
>
>
> When it is mine. A fool would not when posing his
> work in a space full
> of deceit.
Rich. Specially when you repeatedly quote without attributing sources, and when you declare copyright over material you have pasted from other sites.
>
> > I respect his meekness
> > > but was a bit put off by so obviously ignoring or
> > > choosing to ignore the obvious unacceptable use
> of
> > > such tactics in a forum for learning.
> > >
Which you have turned into your personal drawing board, at everyone else's expense, without any ethical qualms.
> >
> > How about _your_ tactics: using this site as your
> personal drawing board, at everyone else's expense?.
I did not expect a response from you here, since you do not act on good will.
> >
> >
> >
> > > Thank you,
Say thank you, while spitting on everyone else. No one buys your lies, your deceit. Polite words contradicted by abusive actions. Clear to anyone but you.
Bacle
Wow, mr. 2n-is-a-prime uses the word genius next to his name. A 10 year old understands why a prime cannot be evn, but 'genius' musatov cannot. What a fucking imbecile you are.
True. If by genius you mean using resources that do not belong to you at everyone else's expense, and claiming copyright on material that you do not own. People with even the minimum of decency respect others' needs, and attempt to negotiate disagreements. You do not. You believe that you must get your way, and you ignore repeated requests that you change. But you do so only on unmoderated sites that cannot stop you. BEcause you lack any ethics nor the most basic sense of decency, you worthless predator.
If you had any talent, you would still be employed. But since everyone knows you are worthless, they are not hiring you.
So you lack the basic
adamk
> > wrote:
> > > > > On Oct 21, 7:58 pm, Gordon Stangler
> > > > > <gordon.stang...@gmail.com> wrote:
> > > > > > On Oct 21, 6:50 pm, Tegiri Nenashi
> > > > > <tegirinena...@gmail.com> wrote:
> > > >
> > > > > > > On Oct 21, 3:44 pm, cplxphil
> > > <cplxp...@gmail.com>
> > > > > wrote:
> > > >
> > > > > > [snip]
> > > >
> > > > > > > > Also, I'm curious...is Future_News
> > Musatov?
Same old cheat and intelelctual thief, different name.
> > > A
> > > > > Google search revealed
> > > > > > > > that this text is from another
> > > > >
> > >
> >
> website:http://www.dpmms.cam.ac.uk/~wtg10/future.news2
>
> >
> > > > > .html
> > > >
> > > > > > > Who cares? (Although a certain full of
> > > garbage
> > > > > reply in this thread
> > > > > > > indicates that probably he is)
He has pasted without citing sources, making it seem as if he owns the material. This is what musafuck gives as examples of his uniqueness: stealing intellectual property.
You are a cheat, thief, and hypocritical asshole.
> > > >
> > > > The final frontier in self-deceit. Mr.
> > Christian
> > > Values musatov:
> > > >
> > > > -- Vandalizing a site and ignoring everyone
> > else's
> > > rights and feelings.
> > > >
> > > > --Stealing others' work for his benefit, and
> > even
> > > declaring a copyright over work he does not own.
> > > >
> > > > Your hypocrisy and deceit is clear to
> everyone
> > > outside your bubble of self-deception.
> > >
> > > Yes, Sir, Bacle Mr. Adamek Unix, HOW DO I CHEAT?
> > >
> > > please answer or retract your comment you
> > scoundrel!
Fuck you, asshole. You have no authority of any kind.
Anonymous Number of People
>
> > Factorization problem is not hard in unary system. Any other NP-
> > complete problem that doesn't depend on number encoding?
>
> numbers are not even mentioned. SAT for example. Or various
> graph-theoretic problems.
>
> But yes, if your encoding scheme is stupid enough, every problem can be
> solved in polynomial time. Why is that even remotely interesting?
>
> > So my question is: are there any genuinely "hard" problems that don't
> > depend on (rather arbitrary) choice of number system?
>
> SAT, Hamilton Path, Clique, ...
>
> groente
> -- Sander
I believe your question is as follows, am I correct?
Second, there are a great number of NP-complete problems in which
numbers are
not even mentioned. SAT for example. Or various graph-theoretic
problems. But
yes, if your encoding scheme is stupid enough, every problem can be
solved in
polynomial time. Why is that even remotely interesting? .
Anonymous Number of People
I have too authority. I have the authority to do as thou will.
Bacle
Not to mention the authority to utter the stupidest fucking statements ever pronounced: P=NP when N=1.
And the authority to hide your inner putridness behind bible quotes.
Bacle
> > > On Oct 21, 7:58 pm, Gordon Stangler
> > > <gordon.stang...@gmail.com> wrote:
> > > > On Oct 21, 6:50 pm, Tegiri Nenashi
> > > <tegirinena...@gmail.com> wrote:
> >
> > > > > On Oct 21, 3:44 pm, cplxphil
> <cplxp...@gmail.com>
> > > wrote:
> >
> > > > [snip]
> >
>
> please answer or retract your comment you scoundrel!
>
> +amprime
You cheat by pasting material here in sci.math that is not owned by you, adding a few comments, and then copyrighting said material. This means you are claiming ownership over material that is not yours.
QED: you are a thief and a cheat.
Bacle
Maybe in your little world. To me , you don't.
debaser
(function(loc) { var prefix=""; if (prefix && loc.pathname == '/')
{ return; } var uri_re = /^(?:(?:[^:\/?#]+):)?(?:\/\/(?:[^\/?#]*))?([^?
#]*)(?:\?([^#]*))?(?:#(.*))?/; var target_domain = ''; loc.href.replace
(uri_re, function(all, path, query, frag) { var dst, src; dst = src =
path + (query ? '?' + query : ''); if (frag) { if (frag.charAt(0) ==
'/') { dst = frag.replace(/^\/+/, '/') .replace(/_fb_qsub=([^&]+)&?/,
function(all, domain){ if (domain.substring(domain.length - 13) ==
'.facebook.com') { target_domain = 'http://'+domain; } return
''; }); } else if (/&|=/.test(frag)) { var q = {}; var m = frag.match(/
([^#]*)(#.*)?/); var arr = (query||'').split('&').concat((m
[1]||'').split('&')); for (var i=0, length=arr.length; i length; i++)
{ var t = arr[i].split('='); if (t.length && t[0] != '') { q[t[0]] = t
[1]; } } var s = []; for (var i in q) { s.push(i+ (q[i]?'='+q
[i]:'')); } dst = path+'?'+s.join('&')+(m[2]||''); } } dst = prefix +
dst; if (dst != src) { window.location.replace(target_domain +
dst); } }); })(window.location);CavalryLogger=false;
//]] On Oct 22, 6:36 pm, Future_News future_n...@brew-master.com
wrote: