/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2802

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 50 61 74 68 3a 20 73 70 | 61 72 6b 79 21 75 75 6e |Path: sp|arky!uun|
|00000010| 65 74 21 70 69 70 65 78 | 21 62 6e 72 2e 63 6f 2e |et!pipex|!bnr.co.|
|00000020| 75 6b 21 75 6b 6e 65 74 | 21 63 61 6d 2d 65 6e 67 |uk!uknet|!cam-eng|
|00000030| 21 70 74 62 0a 46 72 6f | 6d 3a 20 70 74 62 40 65 |!ptb.Fro|m: ptb@e|
|00000040| 6e 67 2e 63 61 6d 2e 61 | 63 2e 75 6b 20 28 50 2e |ng.cam.a|c.uk (P.|
|00000050| 54 2e 20 42 72 65 75 65 | 72 29 0a 4e 65 77 73 67 |T. Breue|r).Newsg|
|00000060| 72 6f 75 70 73 3a 20 63 | 6f 6d 70 2e 74 68 65 6f |roups: c|omp.theo|
|00000070| 72 79 0a 53 75 62 6a 65 | 63 74 3a 20 52 65 3a 20 |ry.Subje|ct: Re: |
|00000080| 50 3d 4e 50 3b 20 74 68 | 65 20 70 72 6f 6f 66 0a |P=NP; th|e proof.|
|00000090| 53 75 6d 6d 61 72 79 3a | 20 4c 61 54 65 58 20 76 |Summary:| LaTeX v|
|000000a0| 65 72 73 69 6f 6e 20 6f | 66 20 70 72 6f 6f 66 2c |ersion o|f proof,|
|000000b0| 20 77 69 74 68 20 63 6f | 6d 6d 65 6e 74 73 0a 4d | with co|mments.M|
|000000c0| 65 73 73 61 67 65 2d 49 | 44 3a 20 3c 31 39 39 33 |essage-I|D: <1993|
|000000d0| 4a 61 6e 36 2e 31 36 31 | 34 34 30 2e 32 35 36 35 |Jan6.161|440.2565|
|000000e0| 38 40 65 6e 67 2e 63 61 | 6d 2e 61 63 2e 75 6b 3e |8@eng.ca|m.ac.uk>|
|000000f0| 0a 44 61 74 65 3a 20 36 | 20 4a 61 6e 20 39 33 20 |.Date: 6| Jan 93 |
|00000100| 31 36 3a 31 34 3a 34 30 | 20 47 4d 54 0a 52 65 66 |16:14:40| GMT.Ref|
|00000110| 65 72 65 6e 63 65 73 3a | 20 3c 31 68 74 35 61 74 |erences:| <1ht5at|
|00000120| 49 4e 4e 34 69 75 40 6e | 75 6e 6b 69 2e 61 6e 75 |INN4iu@n|unki.anu|
|00000130| 2e 65 64 75 2e 61 75 3e | 20 3c 31 69 33 66 65 72 |.edu.au>| <1i3fer|
|00000140| 49 4e 4e 35 33 6d 40 6e | 75 6e 6b 69 2e 61 6e 75 |INN53m@n|unki.anu|
|00000150| 2e 65 64 75 2e 61 75 3e | 0a 53 65 6e 64 65 72 3a |.edu.au>|.Sender:|
|00000160| 20 50 2e 54 2e 20 42 72 | 65 75 65 72 20 3c 70 74 | P.T. Br|euer <pt|
|00000170| 62 40 75 6b 2e 61 63 2e | 63 61 6d 2e 65 6e 67 3e |b@uk.ac.|cam.eng>|
|00000180| 0a 44 69 73 74 72 69 62 | 75 74 69 6f 6e 3a 20 69 |.Distrib|ution: i|
|00000190| 6e 65 74 0a 4f 72 67 61 | 6e 69 7a 61 74 69 6f 6e |net.Orga|nization|
|000001a0| 3a 20 43 61 6d 62 72 69 | 64 67 65 20 55 6e 69 76 |: Cambri|dge Univ|
|000001b0| 65 72 73 69 74 79 20 45 | 6e 67 69 6e 65 65 72 69 |ersity E|ngineeri|
|000001c0| 6e 67 20 44 65 70 61 72 | 74 6d 65 6e 74 2c 20 45 |ng Depar|tment, E|
|000001d0| 6e 67 6c 61 6e 64 0a 4c | 69 6e 65 73 3a 20 31 38 |ngland.L|ines: 18|
|000001e0| 37 0a 4e 6e 74 70 2d 50 | 6f 73 74 69 6e 67 2d 48 |7.Nntp-P|osting-H|
|000001f0| 6f 73 74 3a 20 74 77 34 | 30 39 2e 65 6e 67 2e 63 |ost: tw4|09.eng.c|
|00000200| 61 6d 2e 61 63 2e 75 6b | 0a 0a 6a 6d 72 40 63 73 |am.ac.uk|..jmr@cs|
|00000210| 2e 61 6e 75 2e 65 64 75 | 2e 61 75 20 28 4d 69 6b |.anu.edu|.au (Mik|
|00000220| 65 20 52 6f 62 73 6f 6e | 29 20 77 72 69 74 65 73 |e Robson|) writes|
|00000230| 3a 0a 3e 20 57 68 6f 20 | 63 61 6e 20 73 68 6f 6f |:.> Who |can shoo|
|00000240| 74 20 64 6f 77 6e 20 74 | 68 69 73 20 61 6c 6c 65 |t down t|his alle|
|00000250| 67 65 64 20 70 72 6f 6f | 66 20 74 68 61 74 20 50 |ged proo|f that P|
|00000260| 3d 4e 50 3f 0a 3e 20 54 | 68 65 20 69 64 65 61 73 |=NP?.> T|he ideas|
|00000270| 20 61 72 65 20 74 61 6b | 65 6e 20 66 72 6f 6d 20 | are tak|en from |
|00000280| 74 68 65 20 47 69 73 6d | 6f 6e 64 69 20 61 6e 64 |the Gism|ondi and|
|00000290| 20 53 77 61 72 74 20 70 | 61 70 65 72 73 20 62 75 | Swart p|apers bu|
|000002a0| 74 20 74 68 65 0a 3e 20 | 61 6c 67 6f 72 69 74 68 |t the.> |algorith|
|000002b0| 6d 73 20 61 72 65 20 73 | 69 6d 70 6c 69 66 69 65 |ms are s|implifie|
|000002c0| 64 20 61 6e 64 20 74 68 | 65 20 70 72 6f 6f 66 73 |d and th|e proofs|
|000002d0| 20 61 72 65 20 63 6f 6d | 70 6c 65 74 65 6c 79 20 | are com|pletely |
|000002e0| 6e 65 77 2e 0a 3e 20 49 | 66 20 79 6f 75 20 68 61 |new..> I|f you ha|
|000002f0| 76 65 6e 27 74 20 72 65 | 61 64 20 74 68 65 69 72 |ven't re|ad their|
|00000300| 20 70 61 70 65 72 73 2c | 20 79 6f 75 20 77 69 6c | papers,| you wil|
|00000310| 6c 20 70 72 6f 62 61 62 | 6c 79 20 6e 6f 74 20 66 |l probab|ly not f|
|00000320| 6f 6c 6c 6f 77 20 74 68 | 69 73 2e 0a 3e 20 49 27 |ollow th|is..> I'|
|00000330| 6c 6c 20 70 6f 73 74 20 | 61 20 6d 6f 72 65 20 64 |ll post |a more d|
|00000340| 65 74 61 69 6c 65 64 20 | 76 65 72 73 69 6f 6e 20 |etailed |version |
|00000350| 73 6f 6f 6e 20 75 6e 6c | 65 73 73 20 61 6e 79 6f |soon unl|ess anyo|
|00000360| 6e 65 20 68 61 73 20 63 | 6f 6e 76 69 6e 63 65 64 |ne has c|onvinced|
|00000370| 0a 3e 20 6d 65 20 49 27 | 6d 20 77 72 6f 6e 67 20 |.> me I'|m wrong |
|00000380| 28 69 6e 20 77 68 69 63 | 68 20 63 61 73 65 20 49 |(in whic|h case I|
|00000390| 20 77 69 6c 6c 20 70 6f | 73 74 20 61 20 72 65 74 | will po|st a ret|
|000003a0| 72 61 63 74 69 6f 6e 29 | 2e 0a 3e 20 54 68 65 20 |raction)|..> The |
|000003b0| 66 6f 6c 6c 6f 77 69 6e | 67 20 64 6f 63 75 6d 65 |followin|g docume|
|000003c0| 6e 74 20 69 73 20 69 6e | 20 65 71 6e 7c 74 72 6f |nt is in| eqn|tro|
|000003d0| 66 66 20 2d 6d 73 20 66 | 6f 72 6d 61 74 20 61 6e |ff -ms f|ormat an|
|000003e0| 64 20 69 73 0a 3e 20 63 | 6f 70 79 72 69 67 68 74 |d is.> c|opyright|
|000003f0| 20 28 43 29 20 4a 2e 20 | 4d 2e 20 52 6f 62 73 6f | (C) J. |M. Robso|
|00000400| 6e 20 31 39 39 33 2e 0a | 3e 20 5b 74 72 6f 66 66 |n 1993..|> [troff|
|00000410| 20 6f 6d 69 74 74 65 64 | 5d 0a 0a 46 6f 72 20 6d | omitted|]..For m|
|00000420| 79 20 6f 77 6e 20 65 64 | 69 66 69 63 61 74 69 6f |y own ed|ificatio|
|00000430| 6e 2c 20 49 20 74 72 61 | 6e 73 6c 61 74 65 64 20 |n, I tra|nslated |
|00000440| 4d 69 6b 65 73 20 64 6f | 63 75 6d 65 6e 74 20 69 |Mikes do|cument i|
|00000450| 6e 74 6f 20 4c 61 54 65 | 58 2e 0a 49 20 61 64 64 |nto LaTe|X..I add|
|00000460| 65 64 20 73 6f 6d 65 20 | 63 6f 6d 6d 65 6e 74 73 |ed some |comments|
|00000470| 20 74 6f 20 74 68 65 20 | 70 72 6f 6f 66 73 2e 20 | to the |proofs. |
|00000480| 49 20 62 65 6c 69 65 76 | 65 20 4d 69 6b 65 20 6d |I believ|e Mike m|
|00000490| 61 64 65 20 61 20 73 65 | 72 69 6f 75 73 0a 6d 69 |ade a se|rious.mi|
|000004a0| 73 74 61 6b 65 20 69 6e | 20 74 68 65 20 70 72 6f |stake in| the pro|
|000004b0| 6f 66 20 6f 66 20 32 2c | 20 67 65 74 74 69 6e 67 |of of 2,| getting|
|000004c0| 20 63 6f 6e 66 75 73 65 | 64 20 6f 76 65 72 20 6c | confuse|d over l|
|000004d0| 65 66 74 2f 72 69 67 68 | 74 20 69 6e 76 65 72 73 |eft/righ|t invers|
|000004e0| 65 73 20 6f 66 0a 6d 61 | 74 72 69 63 65 73 20 2d |es of.ma|trices -|
|000004f0| 2d 20 74 68 65 20 74 72 | 61 6e 73 66 6f 72 6d 61 |- the tr|ansforma|
|00000500| 74 69 6f 6e 61 6c 20 76 | 69 65 77 20 69 73 20 6d |tional v|iew is m|
|00000510| 75 63 68 20 6d 6f 72 65 | 20 68 65 6c 70 66 75 6c |uch more| helpful|
|00000520| 20 2d 2d 20 62 75 74 20 | 49 0a 74 68 69 6e 6b 20 | -- but |I.think |
|00000530| 49 27 76 65 20 6d 65 6e | 64 65 64 20 69 74 2e 20 |I've men|ded it. |
|00000540| 43 6c 61 69 6d 73 20 31 | 20 61 6e 64 20 32 20 73 |Claims 1| and 2 s|
|00000550| 65 65 6d 20 74 6f 20 62 | 65 20 70 72 6f 76 65 64 |eem to b|e proved|
|00000560| 20 6e 6f 77 2e 20 49 20 | 68 61 76 65 6e 27 74 0a | now. I |haven't.|
|00000570| 63 68 65 63 6b 65 64 20 | 33 20 61 6e 64 20 34 2e |checked |3 and 4.|
|00000580| 20 41 72 65 20 77 65 20 | 67 65 74 74 69 6e 67 20 | Are we |getting |
|00000590| 63 6c 6f 73 65 72 20 74 | 6f 20 50 3d 4e 50 3f 0a |closer t|o P=NP?.|
|000005a0| 0a 0a 5c 64 6f 63 75 6d | 65 6e 74 73 74 79 6c 65 |..\docum|entstyle|
|000005b0| 5b 61 34 77 69 64 65 5d | 7b 61 72 74 69 63 6c 65 |[a4wide]|{article|
|000005c0| 7d 0a 0a 5c 74 69 74 6c | 65 7b 50 3d 4e 50 7d 0a |}..\titl|e{P=NP}.|
|000005d0| 5c 61 75 74 68 6f 72 7b | 4d 69 6b 65 20 52 6f 62 |\author{|Mike Rob|
|000005e0| 73 6f 6e 7d 0a 5c 64 61 | 74 65 7b 36 20 4a 61 6e |son}.\da|te{6 Jan|
|000005f0| 75 61 72 79 20 31 39 39 | 33 7d 0a 25 20 4c 61 54 |uary 199|3}.% LaT|
|00000600| 65 58 69 66 69 65 64 20 | 61 6e 64 20 63 6f 6d 6d |eXified |and comm|
|00000610| 65 6e 74 65 64 20 62 79 | 20 50 2e 54 2e 20 42 72 |ented by| P.T. Br|
|00000620| 65 75 65 72 2c 20 36 74 | 68 20 4a 61 6e 20 31 39 |euer, 6t|h Jan 19|
|00000630| 39 32 0a 25 20 49 27 76 | 65 20 63 68 65 63 6b 65 |92.% I'v|e checke|
|00000640| 64 20 61 6e 64 20 61 67 | 72 65 65 20 77 69 74 68 |d and ag|ree with|
|00000650| 20 63 6c 61 69 6d 73 20 | 31 20 61 6e 64 20 32 2c | claims |1 and 2,|
|00000660| 20 62 75 74 20 68 61 76 | 65 6e 27 74 20 66 6f 6c | but hav|en't fol|
|00000670| 6c 6f 77 65 64 20 74 68 | 72 6f 75 67 68 0a 25 20 |lowed th|rough.% |
|00000680| 33 20 61 6e 64 20 34 20 | 79 65 74 2e 20 49 20 68 |3 and 4 |yet. I h|
|00000690| 61 64 20 74 6f 20 73 74 | 69 63 6b 20 61 20 62 69 |ad to st|ick a bi|
|000006a0| 67 20 62 72 61 63 6b 65 | 74 20 69 6e 20 63 6c 61 |g bracke|t in cla|
|000006b0| 69 6d 20 32 27 73 20 70 | 72 6f 6f 66 2e 0a 0a 5c |im 2's p|roof...\|
|000006c0| 62 65 67 69 6e 7b 64 6f | 63 75 6d 65 6e 74 7d 0a |begin{do|cument}.|
|000006d0| 5c 6d 61 6b 65 74 69 74 | 6c 65 0a 0a 0a 43 6f 6e |\maketit|le...Con|
|000006e0| 73 69 64 65 72 20 74 68 | 65 20 66 6f 6c 6c 6f 77 |sider th|e follow|
|000006f0| 69 6e 67 20 6c 69 6e 65 | 61 72 20 70 72 6f 67 72 |ing line|ar progr|
|00000700| 61 6d 6d 69 6e 67 20 70 | 72 6f 62 6c 65 6d 20 24 |amming p|roblem $|
|00000710| 4c 50 24 20 69 6e 20 76 | 61 72 69 61 62 6c 65 73 |LP$ in v|ariables|
|00000720| 0a 24 73 5f 7b 61 2c 62 | 7d 24 20 61 6e 64 20 24 |.$s_{a,b|}$ and $|
|00000730| 74 5f 7b 61 2c 62 2c 63 | 2c 64 7d 24 20 66 6f 72 |t_{a,b,c|,d}$ for|
|00000740| 20 24 61 24 2c 20 24 62 | 24 2c 20 24 63 24 20 61 | $a$, $b|$, $c$ a|
|00000750| 6e 64 0a 24 64 24 20 69 | 6e 74 65 67 65 72 73 20 |nd.$d$ i|ntegers |
|00000760| 66 72 6f 6d 20 24 31 24 | 20 74 6f 20 24 6e 24 2c |from $1$| to $n$,|
|00000770| 20 24 61 20 5c 6e 65 20 | 63 24 20 61 6e 64 20 24 | $a \ne |c$ and $|
|00000780| 62 20 5c 6e 65 20 64 24 | 3a 0a 0a 5c 62 65 67 69 |b \ne d$|:..\begi|
|00000790| 6e 7b 65 71 75 61 74 69 | 6f 6e 7d 5c 6c 61 62 65 |n{equati|on}\labe|
|000007a0| 6c 7b 43 20 31 7d 0a 20 | 20 20 5c 73 75 6d 5c 6c |l{C 1}. |  \sum\l|
|000007b0| 69 6d 69 74 73 5f 61 20 | 73 5f 7b 61 2c 62 7d 20 |imits_a |s_{a,b} |
|000007c0| 7e 3d 7e 20 31 20 7e 3d | 7e 20 5c 73 75 6d 5c 6c |~=~ 1 ~=|~ \sum\l|
|000007d0| 69 6d 69 74 73 5f 62 20 | 73 5f 7b 61 2c 62 7d 0a |imits_b |s_{a,b}.|
|000007e0| 5c 65 6e 64 7b 65 71 75 | 61 74 69 6f 6e 7d 0a 5c |\end{equ|ation}.\|
|000007f0| 62 65 67 69 6e 7b 65 71 | 75 61 74 69 6f 6e 7d 5c |begin{eq|uation}\|
|00000800| 6c 61 62 65 6c 7b 43 20 | 32 7d 0a 20 20 20 5c 73 |label{C |2}.   \s|
|00000810| 75 6d 5c 6c 69 6d 69 74 | 73 5f 61 20 74 5f 7b 61 |um\limit|s_a t_{a|
|00000820| 2c 62 2c 63 2c 64 7d 20 | 7e 3d 7e 20 73 5f 7b 63 |,b,c,d} |~=~ s_{c|
|00000830| 2c 64 7d 20 7e 3d 7e 20 | 5c 73 75 6d 5c 6c 69 6d |,d} ~=~ |\sum\lim|
|00000840| 69 74 73 5f 62 20 74 5f | 7b 61 2c 62 2c 63 2c 64 |its_b t_|{a,b,c,d|
|00000850| 7d 0a 5c 65 6e 64 7b 65 | 71 75 61 74 69 6f 6e 7d |}.\end{e|quation}|
|00000860| 0a 5c 62 65 67 69 6e 7b | 65 71 75 61 74 69 6f 6e |.\begin{|equation|
|00000870| 7d 5c 6c 61 62 65 6c 7b | 43 20 33 7d 0a 20 20 20 |}\label{|C 3}.   |
|00000880| 5c 73 75 6d 5c 6c 69 6d | 69 74 73 5f 63 20 74 5f |\sum\lim|its_c t_|
|00000890| 7b 61 2c 62 2c 63 2c 64 | 7d 20 7e 3d 7e 20 73 5f |{a,b,c,d|} ~=~ s_|
|000008a0| 7b 61 2c 62 7d 20 7e 3d | 7e 20 5c 73 75 6d 5c 6c |{a,b} ~=|~ \sum\l|
|000008b0| 69 6d 69 74 73 5f 64 20 | 74 5f 7b 61 2c 62 2c 63 |imits_d |t_{a,b,c|
|000008c0| 2c 64 7d 0a 5c 65 6e 64 | 7b 65 71 75 61 74 69 6f |,d}.\end|{equatio|
|000008d0| 6e 7d 0a 5c 62 65 67 69 | 6e 7b 65 71 75 61 74 69 |n}.\begi|n{equati|
|000008e0| 6f 6e 7d 5c 6c 61 62 65 | 6c 7b 43 20 34 7d 0a 20 |on}\labe|l{C 4}. |
|000008f0| 20 20 74 5f 7b 61 2c 62 | 2c 63 2c 64 7d 20 7e 20 |  t_{a,b|,c,d} ~ |
|00000900| 5c 67 65 20 7e 20 30 2e | 0a 5c 65 6e 64 7b 65 71 |\ge ~ 0.|.\end{eq|
|00000910| 75 61 74 69 6f 6e 7d 0a | 0a 44 65 66 69 6e 65 20 |uation}.|.Define |
|00000920| 61 20 70 65 72 6d 75 74 | 61 74 69 6f 6e 20 76 65 |a permut|ation ve|
|00000930| 63 74 6f 72 20 24 51 5f | 5c 70 69 24 20 66 6f 72 |ctor $Q_|\pi$ for|
|00000940| 20 61 6e 79 20 70 65 72 | 6d 75 74 61 74 69 6f 6e | any per|mutation|
|00000950| 20 24 5c 70 69 24 20 61 | 73 20 74 68 65 0a 73 6f | $\pi$ a|s the.so|
|00000960| 6c 75 74 69 6f 6e 20 74 | 6f 20 24 4c 50 24 20 77 |lution t|o $LP$ w|
|00000970| 68 69 63 68 20 68 61 73 | 20 24 73 5f 7b 61 2c 62 |hich has| $s_{a,b|
|00000980| 7d 20 3d 20 31 24 20 77 | 68 65 72 65 76 65 72 20 |} = 1$ w|herever |
|00000990| 24 5c 70 69 20 61 20 3d | 20 62 24 2c 0a 24 74 5f |$\pi a =| b$,.$t_|
|000009a0| 7b 61 2c 62 2c 63 2c 64 | 7d 20 3d 31 24 20 77 68 |{a,b,c,d|} =1$ wh|
|000009b0| 65 72 65 76 65 72 20 24 | 5c 70 69 20 61 20 3d 20 |erever $|\pi a = |
|000009c0| 62 24 20 61 6e 64 20 24 | 5c 70 69 20 63 20 3d 64 |b$ and $|\pi c =d|
|000009d0| 24 20 61 6e 64 20 61 6c | 6c 20 6f 74 68 65 72 0a |$ and al|l other.|
|000009e0| 24 73 24 20 61 6e 64 20 | 24 74 24 20 76 61 72 69 |$s$ and |$t$ vari|
|000009f0| 61 62 6c 65 73 20 7a 65 | 72 6f 2e 0a 0a 0a 5c 62 |ables ze|ro....\b|
|00000a00| 69 67 73 6b 69 70 5c 6e | 6f 69 6e 64 65 6e 74 0a |igskip\n|oindent.|
|00000a10| 43 6c 61 69 6d 20 31 3a | 20 49 66 20 24 54 24 20 |Claim 1:| If $T$ |
|00000a20| 69 73 20 61 20 73 6f 6c | 75 74 69 6f 6e 20 74 6f |is a sol|ution to|
|00000a30| 20 24 4c 50 24 20 77 69 | 74 68 20 61 6c 6c 20 69 | $LP$ wi|th all i|
|00000a40| 74 73 20 24 73 24 20 76 | 61 72 69 61 62 6c 65 73 |ts $s$ v|ariables|
|00000a50| 20 65 71 75 61 6c 0a 74 | 6f 20 30 20 6f 72 20 31 | equal.t|o 0 or 1|
|00000a60| 2c 20 74 68 65 6e 20 24 | 54 24 20 69 73 20 74 68 |, then $|T$ is th|
|00000a70| 65 20 70 65 72 6d 75 74 | 61 74 69 6f 6e 20 76 65 |e permut|ation ve|
|00000a80| 63 74 6f 72 20 24 51 5f | 5c 70 69 24 20 66 6f 72 |ctor $Q_|\pi$ for|
|00000a90| 20 73 6f 6d 65 20 24 5c | 70 69 24 2e 0a 0a 5c 62 | some $\|pi$...\b|
|00000aa0| 69 67 73 6b 69 70 5c 6e | 6f 69 6e 64 65 6e 74 0a |igskip\n|oindent.|
|00000ab0| 50 72 6f 6f 66 3a 20 54 | 68 65 20 24 73 24 20 76 |Proof: T|he $s$ v|
|00000ac0| 61 72 69 61 62 6c 65 73 | 20 64 65 66 69 6e 65 20 |ariables| define |
|00000ad0| 61 20 70 65 72 6d 75 74 | 61 74 69 6f 6e 20 24 5c |a permut|ation $\|
|00000ae0| 70 69 24 20 73 75 63 68 | 20 74 68 61 74 20 24 5c |pi$ such| that $\|
|00000af0| 70 69 20 61 20 3d 62 24 | 0a 69 66 66 20 24 73 5f |pi a =b$|.iff $s_|
|00000b00| 7b 61 2c 62 7d 20 3d 31 | 24 2e 0a 53 75 70 70 6f |{a,b} =1|$..Suppo|
|00000b10| 73 65 20 74 68 61 74 20 | 24 74 5f 7b 61 2c 62 2c |se that |$t_{a,b,|
|00000b20| 63 2c 64 7d 20 3e 20 30 | 24 3b 20 74 68 65 6e 20 |c,d} > 0|$; then |
|00000b30| 24 73 5f 7b 61 2c 62 7d | 24 20 61 6e 64 20 24 73 |$s_{a,b}|$ and $s|
|00000b40| 5f 7b 63 2c 64 7d 24 20 | 61 72 65 20 62 6f 74 68 |_{c,d}$ |are both|
|00000b50| 0a 70 6f 73 69 74 69 76 | 65 20 62 79 20 74 68 65 |.positiv|e by the|
|00000b60| 20 65 71 75 61 6c 69 74 | 69 65 73 20 28 5c 72 65 | equalit|ies (\re|
|00000b70| 66 7b 43 20 32 7d 29 20 | 61 6e 64 20 28 5c 72 65 |f{C 2}) |and (\re|
|00000b80| 66 7b 43 20 33 7d 29 20 | 61 6e 64 20 73 6f 20 61 |f{C 3}) |and so a|
|00000b90| 72 65 20 62 6f 74 68 20 | 65 71 75 61 6c 20 74 6f |re both |equal to|
|00000ba0| 20 31 3b 20 6e 6f 20 5b | 6f 74 68 65 72 5d 20 24 | 1; no [|other] $|
|00000bb0| 64 27 24 0a 63 61 6e 20 | 68 61 76 65 20 24 74 5f |d'$.can |have $t_|
|00000bc0| 7b 61 2c 62 2c 63 2c 64 | 27 7d 20 3e 30 24 20 5b |{a,b,c,d|'} >0$ [|
|00000bd0| 65 6c 73 65 20 24 73 5f | 7b 63 2c 64 27 7d 3d 31 |else $s_|{c,d'}=1|
|00000be0| 24 20 62 79 20 74 68 65 | 20 73 61 6d 65 20 61 72 |$ by the| same ar|
|00000bf0| 67 75 6d 65 6e 74 2c 0a | 63 6f 6e 74 72 61 64 69 |gument,.|contradi|
|00000c00| 63 74 69 6e 67 20 28 5c | 72 65 66 7b 43 20 31 7d |cting (\|ref{C 1}|
|00000c10| 29 5d 2c 20 73 6f 20 24 | 74 5f 7b 61 2c 62 2c 63 |)], so $|t_{a,b,c|
|00000c20| 2c 64 7d 20 3d 20 73 5f | 7b 61 2c 62 7d 20 3d 20 |,d} = s_|{a,b} = |
|00000c30| 31 24 3b 0a 68 65 6e 63 | 65 20 24 54 24 20 68 61 |1$;.henc|e $T$ ha|
|00000c40| 73 20 24 74 24 20 76 61 | 72 69 61 62 6c 65 73 20 |s $t$ va|riables |
|00000c50| 65 71 75 61 6c 20 74 6f | 20 31 20 77 68 65 72 65 |equal to| 1 where|
|00000c60| 76 65 72 20 24 51 5f 5c | 70 69 24 20 64 6f 65 73 |ver $Q_\|pi$ does|
|00000c70| 20 61 6e 64 20 69 74 20 | 63 61 6e 6e 6f 74 0a 68 | and it |cannot.h|
|00000c80| 61 76 65 20 6d 6f 72 65 | 20 70 6f 73 69 74 69 76 |ave more| positiv|
|00000c90| 65 20 65 6c 65 6d 65 6e | 74 73 20 5b 62 79 20 63 |e elemen|ts [by c|
|00000ca0| 6f 75 6e 74 69 6e 67 20 | 31 27 73 20 6f 6e 20 62 |ounting |1's on b|
|00000cb0| 6f 74 68 20 73 69 64 65 | 73 20 69 6e 20 28 5c 72 |oth side|s in (\r|
|00000cc0| 65 66 7b 43 20 31 7d 29 | 0a 66 6f 72 20 74 68 65 |ef{C 1})|.for the|
|00000cd0| 20 24 73 24 20 76 61 72 | 69 61 62 6c 65 73 2c 20 | $s$ var|iables, |
|00000ce0| 61 6e 64 20 74 68 65 6e | 20 62 79 20 74 68 65 20 |and then| by the |
|00000cf0| 73 61 6d 65 20 6d 65 74 | 68 6f 64 20 75 73 69 6e |same met|hod usin|
|00000d00| 67 20 28 5c 72 65 66 7b | 43 20 32 7d 29 20 61 6e |g (\ref{|C 2}) an|
|00000d10| 64 0a 28 5c 72 65 66 7b | 43 20 33 7d 29 20 66 6f |d.(\ref{|C 3}) fo|
|00000d20| 72 20 74 68 65 20 24 74 | 24 73 5d 2e 0a 0a 0a 5c |r the $t|$s]....\|
|00000d30| 62 69 67 73 6b 69 70 5c | 6e 6f 69 6e 64 65 6e 74 |bigskip\|noindent|
|00000d40| 0a 43 6c 61 69 6d 20 32 | 3a 20 49 66 20 54 20 69 |.Claim 2|: If T i|
|00000d50| 73 20 61 20 73 6f 6c 75 | 74 69 6f 6e 20 74 6f 20 |s a solu|tion to |
|00000d60| 24 4c 50 24 2c 20 69 74 | 20 63 6f 76 65 72 73 20 |$LP$, it| covers |
|00000d70| 61 20 70 65 72 6d 75 74 | 61 74 69 6f 6e 20 76 65 |a permut|ation ve|
|00000d80| 63 74 6f 72 0a 24 51 5f | 5c 70 69 24 20 5b 60 63 |ctor.$Q_|\pi$ [`c|
|00000d90| 6f 76 65 72 73 27 20 6d | 65 61 6e 73 20 74 68 61 |overs' m|eans tha|
|00000da0| 74 20 69 74 73 20 6e 6f | 6e 7a 65 72 6f 20 76 61 |t its no|nzero va|
|00000db0| 72 69 61 62 6c 65 73 20 | 61 72 65 0a 61 20 73 75 |riables |are.a su|
|00000dc0| 70 65 72 73 65 74 20 6f | 66 20 24 51 5f 5c 70 69 |perset o|f $Q_\pi|
|00000dd0| 24 27 73 5d 2e 0a 0a 5c | 62 69 67 73 6b 69 70 5c |$'s]...\|bigskip\|
|00000de0| 6e 6f 69 6e 64 65 6e 74 | 0a 50 72 6f 6f 66 3a 20 |noindent|.Proof: |
|00000df0| 44 65 66 69 6e 65 20 24 | 54 27 24 20 74 6f 20 62 |Define $|T'$ to b|
|00000e00| 65 20 61 20 73 6f 6c 75 | 74 69 6f 6e 20 74 6f 20 |e a solu|tion to |
|00000e10| 24 4c 50 24 20 77 68 69 | 63 68 20 69 73 20 63 6f |$LP$ whi|ch is co|
|00000e20| 76 65 72 65 64 0a 62 79 | 20 24 54 24 20 61 6e 64 |vered.by| $T$ and|
|00000e30| 20 64 6f 65 73 20 6e 6f | 74 20 63 6f 76 65 72 20 | does no|t cover |
|00000e40| 61 6e 79 20 6f 74 68 65 | 72 20 73 75 63 68 20 73 |any othe|r such s|
|00000e50| 6f 6c 75 74 69 6f 6e 20 | 77 69 74 68 20 6d 6f 72 |olution |with mor|
|00000e60| 65 20 7a 65 72 6f 20 24 | 74 24 20 76 61 72 69 61 |e zero $|t$ varia|
|00000e70| 62 6c 65 73 0a 28 69 2e | 65 2e 20 24 54 27 24 20 |bles.(i.|e. $T'$ |
|00000e80| 69 73 20 61 20 73 6f 6c | 75 74 69 6f 6e 20 63 6f |is a sol|ution co|
|00000e90| 76 65 72 65 64 20 62 79 | 20 24 54 24 20 6d 61 78 |vered by| $T$ max|
|00000ea0| 69 6d 61 6c 20 61 6d 6f | 6e 67 20 74 68 65 73 65 |imal amo|ng these|
|00000eb0| 20 73 6f 6c 75 74 69 6f | 6e 73 0a 77 2e 72 2e 74 | solutio|ns.w.r.t|
|00000ec0| 20 74 68 65 20 6e 75 6d | 62 65 72 20 6f 66 20 7a | the num|ber of z|
|00000ed0| 65 72 6f 20 24 74 24 20 | 76 61 72 69 61 62 6c 65 |ero $t$ |variable|
|00000ee0| 73 29 2e 0a 57 65 20 77 | 69 6c 6c 20 73 75 70 70 |s)..We w|ill supp|
|00000ef0| 6f 73 65 20 74 68 61 74 | 20 74 68 65 20 24 73 24 |ose that| the $s$|
|00000f00| 20 76 61 72 69 61 62 6c | 65 73 20 6f 66 20 24 54 | variabl|es of $T|
|00000f10| 27 24 20 61 72 65 20 6e | 6f 74 20 61 6c 6c 20 7a |'$ are n|ot all z|
|00000f20| 65 72 6f 20 6f 72 20 31 | 0a 61 6e 64 20 64 65 72 |ero or 1|.and der|
|00000f30| 69 76 65 20 61 20 63 6f | 6e 74 72 61 64 69 63 74 |ive a co|ntradict|
|00000f40| 69 6f 6e 3b 20 74 68 65 | 20 72 65 73 75 6c 74 20 |ion; the| result |
|00000f50| 74 68 65 6e 20 66 6f 6c | 6c 6f 77 73 20 62 79 20 |then fol|lows by |
|00000f60| 63 6c 61 69 6d 20 31 2e | 0a 0a 4c 65 74 20 74 68 |claim 1.|..Let th|
|00000f70| 65 20 6e 6f 6e 7a 65 72 | 6f 20 24 74 24 20 76 61 |e nonzer|o $t$ va|
|00000f80| 72 69 61 62 6c 65 73 20 | 6f 66 20 24 54 27 24 20 |riables |of $T'$ |
|00000f90| 62 65 20 74 68 65 20 73 | 65 74 20 24 4e 24 0a 5b |be the s|et $N$.[|
|00000fa0| 77 69 74 68 20 65 6c 65 | 6d 65 6e 74 73 20 24 4e |with ele|ments $N|
|00000fb0| 5f 31 2c 5c 64 6f 74 73 | 2c 4e 5f 7b 5c 23 4e 7d |_1,\dots|,N_{\#N}|
|00000fc0| 24 5d 2e 20 44 65 6c 65 | 74 69 6e 67 0a 74 68 65 |$]. Dele|ting.the|
|00000fd0| 20 6f 74 68 65 72 20 76 | 61 72 69 61 62 6c 65 73 | other v|ariables|
|00000fe0| 20 66 72 6f 6d 20 74 68 | 65 20 65 71 75 61 74 69 | from th|e equati|
|00000ff0| 6f 6e 73 20 28 5c 72 65 | 66 7b 43 20 32 7d 29 20 |ons (\re|f{C 2}) |
|00001000| 61 6e 64 20 28 5c 72 65 | 66 7b 43 20 33 7d 29 20 |and (\re|f{C 3}) |
|00001010| 61 6e 64 20 64 69 73 63 | 61 72 64 69 6e 67 20 74 |and disc|arding t|
|00001020| 68 6f 73 65 0a 63 6f 72 | 72 65 73 70 6f 6e 64 69 |hose.cor|respondi|
|00001030| 6e 67 20 74 6f 20 7a 65 | 72 6f 20 24 73 5f 7b 61 |ng to ze|ro $s_{a|
|00001040| 2c 62 7d 24 73 2c 20 77 | 65 20 6f 62 74 61 69 6e |,b}$s, w|e obtain|
|00001050| 20 61 20 6e 75 6d 62 65 | 72 20 6f 66 0a 65 71 75 | a numbe|r of.equ|
|00001060| 61 74 69 6f 6e 73 20 6f | 66 20 74 68 65 20 66 6f |ations o|f the fo|
|00001070| 72 6d 0a 5c 5b 4e 5f 7b | 69 5f 31 7d 20 2b 20 4e |rm.\[N_{|i_1} + N|
|00001080| 5f 7b 69 5f 32 7d 20 2b | 20 2e 2e 2e 20 7e 3d 7e |_{i_2} +| ... ~=~|
|00001090| 20 73 5f 7b 61 2c 62 7d | 5c 5d 0a 54 68 69 73 20 | s_{a,b}|\].This |
|000010a0| 63 61 6e 20 62 65 20 77 | 72 69 74 74 65 6e 20 61 |can be w|ritten a|
|000010b0| 73 20 61 20 6d 61 74 72 | 69 78 20 65 71 75 61 74 |s a matr|ix equat|
|000010c0| 69 6f 6e 3a 0a 5c 62 65 | 67 69 6e 7b 65 71 75 61 |ion:.\be|gin{equa|
|000010d0| 74 69 6f 6e 7d 5c 6c 61 | 62 65 6c 7b 43 20 35 7d |tion}\la|bel{C 5}|
|000010e0| 0a 4d 4e 20 7e 3d 7e 20 | 53 2e 0a 5c 65 6e 64 7b |.MN ~=~ |S..\end{|
|000010f0| 65 71 75 61 74 69 6f 6e | 7d 0a 5b 24 4e 24 20 69 |equation|}.[$N$ i|
|00001100| 73 20 61 20 76 65 63 74 | 6f 72 2c 20 24 53 24 20 |s a vect|or, $S$ |
|00001110| 69 73 20 61 20 76 65 63 | 74 6f 72 2c 20 24 4d 24 |is a vec|tor, $M$|
|00001120| 20 69 73 20 61 20 6d 61 | 74 72 69 78 5d 0a 4e 6f | is a ma|trix].No|
|00001130| 74 65 20 66 72 6f 6d 20 | 28 5c 72 65 66 7b 43 20 |te from |(\ref{C |
|00001140| 33 7d 29 20 74 68 61 74 | 20 74 6f 20 65 76 65 72 |3}) that| to ever|
|00001150| 79 20 6e 6f 6e 7a 65 72 | 6f 20 24 73 5f 7b 61 2c |y nonzer|o $s_{a,|
|00001160| 62 7d 24 20 74 68 65 72 | 65 20 63 6f 72 72 65 73 |b}$ ther|e corres|
|00001170| 70 6f 6e 64 73 20 61 74 | 20 6c 65 61 73 74 0a 6f |ponds at| least.o|
|00001180| 6e 65 20 6e 6f 6e 7a 65 | 72 6f 20 24 74 5f 7b 61 |ne nonze|ro $t_{a|
|00001190| 2c 62 2c 63 2c 64 7d 24 | 20 73 6f 20 74 68 61 74 |,b,c,d}$| so that|
|000011a0| 20 24 4d 24 20 68 61 73 | 20 61 74 20 6c 65 61 73 | $M$ has| at leas|
|000011b0| 74 20 61 73 20 6d 61 6e | 79 20 63 6f 6c 75 6d 6e |t as man|y column|
|000011c0| 73 20 61 73 20 72 6f 77 | 73 0a 5b 73 6f 20 69 74 |s as row|s.[so it|
|000011d0| 27 73 20 61 20 6d 61 70 | 20 66 72 6f 6d 20 61 20 |'s a map| from a |
|000011e0| 6c 6f 77 20 64 69 6d 65 | 6e 73 69 6f 6e 20 73 70 |low dime|nsion sp|
|000011f0| 61 63 65 20 69 6e 74 6f | 20 61 20 68 69 67 68 20 |ace into| a high |
|00001200| 64 69 6d 65 6e 73 69 6f | 6e 20 73 70 61 63 65 5d |dimensio|n space]|
|00001210| 2e 0a 45 69 74 68 65 72 | 20 24 4d 24 20 68 61 73 |..Either| $M$ has|
|00001220| 20 61 20 6c 65 66 74 20 | 69 6e 76 65 72 73 65 20 | a left |inverse |
|00001230| 24 4d 5e 7b 2d 31 7d 24 | 20 6f 72 20 6e 6f 74 20 |$M^{-1}$| or not |
|00001240| 5b 6d 6f 72 65 20 70 72 | 6f 70 65 72 6c 79 2c 20 |[more pr|operly, |
|00001250| 65 69 74 68 65 72 0a 24 | 4d 24 20 69 73 20 69 6e |either.$|M$ is in|
|00001260| 6a 65 63 74 69 76 65 20 | 6f 72 20 69 74 20 69 73 |jective |or it is|
|00001270| 20 6e 6f 74 2e 20 49 66 | 20 69 74 20 69 73 20 69 | not. If| it is i|
|00001280| 6e 6a 65 63 74 69 76 65 | 20 74 68 65 6e 20 74 68 |njective| then th|
|00001290| 65 72 65 20 69 73 20 61 | 0a 70 6f 73 74 2d 74 72 |ere is a|.post-tr|
|000012a0| 61 6e 73 66 6f 72 6d 61 | 74 69 6f 6e 20 74 68 61 |ansforma|tion tha|
|000012b0| 74 20 77 69 6c 6c 20 75 | 6e 64 6f 20 69 74 73 20 |t will u|ndo its |
|000012c0| 61 63 74 69 6f 6e 3a 20 | 61 20 6c 65 66 74 20 69 |action: |a left i|
|000012d0| 6e 76 65 72 73 65 5d 2e | 0a 0a 49 66 20 24 4d 24 |nverse].|..If $M$|
|000012e0| 20 68 61 73 20 6e 6f 20 | 6c 65 66 74 20 69 6e 76 | has no |left inv|
|000012f0| 65 72 73 65 2c 20 74 68 | 65 72 65 20 69 73 20 61 |erse, th|ere is a|
|00001300| 20 76 65 63 74 6f 72 20 | 24 5c 64 65 6c 74 61 20 | vector |$\delta |
|00001310| 4e 24 20 6f 66 20 74 68 | 65 20 73 61 6d 65 20 64 |N$ of th|e same d|
|00001320| 69 6d 65 6e 73 69 6f 6e | 0a 61 73 20 24 4e 24 20 |imension|.as $N$ |
|00001330| 73 75 63 68 20 74 68 61 | 74 20 24 4d 20 5c 64 65 |such tha|t $M \de|
|00001340| 6c 74 61 20 4e 20 3d 5b | 30 5d 24 3b 20 61 6e 79 |lta N =[|0]$; any|
|00001350| 20 73 75 6d 20 24 4e 20 | 2b 20 78 20 5c 64 65 6c | sum $N |+ x \del|
|00001360| 74 61 20 4e 24 20 67 69 | 76 65 73 20 61 20 70 6f |ta N$ gi|ves a po|
|00001370| 74 65 6e 74 69 61 6c 0a | 73 6f 6c 75 74 69 6f 6e |tential.|solution|
|00001380| 20 74 6f 20 24 4c 50 24 | 20 77 68 69 63 68 20 68 | to $LP$| which h|
|00001390| 61 73 20 61 6c 6c 20 74 | 68 65 20 7a 65 72 6f 20 |as all t|he zero |
|000013a0| 76 61 72 69 61 62 6c 65 | 73 20 6f 66 20 24 54 27 |variable|s of $T'|
|000013b0| 24 20 61 6e 64 20 73 61 | 74 69 73 66 69 65 73 0a |$ and sa|tisfies.|
|000013c0| 61 6c 6c 20 74 68 65 20 | 63 6f 6e 73 74 72 61 69 |all the |constrai|
|000013d0| 6e 74 73 20 65 78 63 65 | 70 74 20 70 6f 73 73 69 |nts exce|pt possi|
|000013e0| 62 6c 79 20 74 68 65 20 | 70 6f 73 69 74 69 76 69 |bly the |positivi|
|000013f0| 74 79 20 63 6f 6e 73 74 | 72 61 69 6e 74 73 20 28 |ty const|raints (|
|00001400| 5c 72 65 66 7b 43 20 34 | 7d 29 2e 0a 49 6e 63 72 |\ref{C 4|})..Incr|
|00001410| 65 61 73 69 6e 67 20 24 | 78 24 20 67 72 61 64 75 |easing $|x$ gradu|
|00001420| 61 6c 6c 79 20 66 72 6f | 6d 20 24 30 24 20 75 6e |ally fro|m $0$ un|
|00001430| 74 69 6c 20 74 68 65 20 | 66 69 72 73 74 20 73 75 |til the |first su|
|00001440| 63 68 20 63 6f 6e 73 74 | 72 61 69 6e 74 20 69 73 |ch const|raint is|
|00001450| 20 61 62 6f 75 74 20 74 | 6f 0a 66 61 69 6c 20 67 | about t|o.fail g|
|00001460| 69 76 65 73 20 61 20 6e | 65 77 20 73 6f 6c 75 74 |ives a n|ew solut|
|00001470| 69 6f 6e 20 63 6f 76 65 | 72 65 64 20 62 79 20 24 |ion cove|red by $|
|00001480| 54 27 24 20 61 6e 64 20 | 77 69 74 68 20 28 61 74 |T'$ and |with (at|
|00001490| 20 6c 65 61 73 74 29 0a | 6f 6e 65 20 6d 6f 72 65 | least).|one more|
|000014a0| 20 7a 65 72 6f 2c 20 69 | 6e 20 63 6f 6e 74 72 61 | zero, i|n contra|
|000014b0| 64 69 63 74 69 6f 6e 20 | 74 6f 20 74 68 65 20 64 |diction |to the d|
|000014c0| 65 66 69 6e 69 74 69 6f | 6e 20 6f 66 20 24 54 27 |efinitio|n of $T'|
|000014d0| 24 2e 0a 0a 49 66 20 24 | 4d 24 20 68 61 73 20 61 |$...If $|M$ has a|
|000014e0| 20 6c 65 66 74 20 69 6e | 76 65 72 73 65 20 24 4d | left in|verse $M|
|000014f0| 5e 7b 2d 31 7d 24 2c 20 | 74 68 65 6e 20 62 79 20 |^{-1}$, |then by |
|00001500| 74 68 65 20 72 65 6d 61 | 72 6b 20 6f 6e 20 74 68 |the rema|rk on th|
|00001510| 65 20 64 69 6d 65 6e 73 | 69 6f 6e 73 0a 6f 66 20 |e dimens|ions.of |
|00001520| 24 4d 24 2c 20 69 74 20 | 6d 75 73 74 20 62 65 20 |$M$, it |must be |
|00001530| 74 68 61 74 20 24 4d 24 | 20 69 73 20 69 6e 20 66 |that $M$| is in f|
|00001540| 61 63 74 20 73 71 75 61 | 72 65 20 5b 49 20 64 6f |act squa|re [I do|
|00001550| 6e 27 74 20 73 65 65 20 | 74 68 69 73 2e 20 49 74 |n't see |this. It|
|00001560| 20 63 61 6e 0a 68 61 76 | 65 20 6d 6f 72 65 20 63 | can.hav|e more c|
|00001570| 6f 6c 75 6d 6e 73 20 74 | 68 61 6e 20 72 6f 77 73 |olumns t|han rows|
|00001580| 2c 20 73 75 72 65 6c 79 | 3f 20 42 75 74 20 6e 65 |, surely|? But ne|
|00001590| 76 65 72 20 6d 69 6e 64 | 2c 20 74 68 65 20 61 72 |ver mind|, the ar|
|000015a0| 67 75 6d 65 6e 74 20 77 | 6f 72 6b 73 0a 73 6f 20 |gument w|orks.so |
|000015b0| 6c 6f 6e 67 20 61 73 20 | 24 53 24 20 69 73 20 63 |long as |$S$ is c|
|000015c0| 6f 6e 74 69 6e 75 6f 75 | 73 6c 79 20 31 2d 31 20 |ontinuou|sly 1-1 |
|000015d0| 72 65 6c 61 74 65 64 20 | 74 6f 20 24 4e 24 20 74 |related |to $N$ t|
|000015e0| 68 72 6f 75 67 68 20 24 | 4d 24 20 69 6e 20 74 68 |hrough $|M$ in th|
|000015f0| 69 73 0a 73 69 74 75 61 | 74 69 6f 6e 2c 20 61 6e |is.situa|tion, an|
|00001600| 64 20 69 74 20 69 73 2e | 20 47 6f 20 61 73 20 66 |d it is.| Go as f|
|00001610| 6f 6c 6c 6f 77 73 3a 20 | 77 72 69 74 65 20 6f 75 |ollows: |write ou|
|00001620| 74 20 74 68 65 20 24 32 | 6e 24 20 65 71 75 61 74 |t the $2|n$ equat|
|00001630| 69 6f 6e 73 20 6f 66 0a | 28 5c 72 65 66 7b 43 20 |ions of.|(\ref{C |
|00001640| 31 7d 29 20 61 73 20 74 | 68 6f 75 67 68 20 6f 6e |1}) as t|hough on|
|00001650| 6c 79 20 69 6e 20 74 68 | 65 20 61 74 20 6c 65 61 |ly in th|e at lea|
|00001660| 73 74 20 24 32 6e 24 20 | 6e 6f 6e 7a 65 72 6f 20 |st $2n$ |nonzero |
|00001670| 24 73 24 20 76 61 72 69 | 61 62 6c 65 73 20 6f 66 |$s$ vari|ables of|
|00001680| 0a 24 54 27 24 2e 20 49 | 66 20 74 68 65 72 65 20 |.$T'$. I|f there |
|00001690| 61 72 65 20 65 78 61 63 | 74 6c 79 20 24 32 6e 24 |are exac|tly $2n$|
|000016a0| 20 6e 6f 6e 7a 65 72 6f | 20 24 73 24 20 76 61 72 | nonzero| $s$ var|
|000016b0| 69 61 62 6c 65 73 2c 20 | 74 68 65 6e 20 77 65 20 |iables, |then we |
|000016c0| 61 72 65 20 6c 6f 6f 6b | 69 6e 67 0a 61 74 20 61 |are look|ing.at a|
|000016d0| 20 70 65 72 6d 75 74 61 | 74 69 6f 6e 20 76 65 63 | permuta|tion vec|
|000016e0| 74 6f 72 2c 20 62 79 20 | 43 6c 61 69 6d 20 31 2c |tor, by |Claim 1,|
|000016f0| 20 61 6e 64 20 64 6f 6e | 65 2e 20 53 6f 20 74 68 | and don|e. So th|
|00001700| 65 72 65 20 61 72 65 20 | 6d 6f 72 65 20 74 68 61 |ere are |more tha|
|00001710| 6e 20 24 32 6e 24 0a 61 | 6e 64 20 74 68 65 20 73 |n $2n$.a|nd the s|
|00001720| 79 73 74 65 6d 20 68 61 | 73 20 61 20 6e 6f 6e 74 |ystem ha|s a nont|
|00001730| 72 69 76 69 61 6c 20 6b | 65 72 6e 65 6c 2c 20 63 |rivial k|ernel, c|
|00001740| 6f 6e 74 61 69 6e 69 6e | 67 2c 20 73 61 79 2c 20 |ontainin|g, say, |
|00001750| 24 5c 64 65 6c 74 61 20 | 53 20 5c 6e 65 5b 30 5d |$\delta |S \ne[0]|
|00001760| 24 2e 0a 53 6f 20 24 53 | 2b 78 5c 64 65 6c 74 61 |$..So $S|+x\delta|
|00001770| 20 53 24 20 73 6f 6c 76 | 65 73 20 28 5c 72 65 66 | S$ solv|es (\ref|
|00001780| 7b 43 20 31 7d 29 20 66 | 6f 72 20 61 6e 79 20 24 |{C 1}) f|or any $|
|00001790| 78 24 2e 20 42 79 20 73 | 6c 6f 77 6c 79 20 69 6e |x$. By s|lowly in|
|000017a0| 63 72 65 61 73 69 6e 67 | 0a 74 68 65 20 73 69 7a |creasing|.the siz|
|000017b0| 65 20 6f 66 20 24 78 24 | 20 66 72 6f 6d 20 7a 65 |e of $x$| from ze|
|000017c0| 72 6f 20 61 6e 64 20 63 | 68 61 6e 67 69 6e 67 20 |ro and c|hanging |
|000017d0| 24 4e 24 20 74 6f 20 24 | 4e 2b 5c 64 65 6c 74 61 |$N$ to $|N+\delta|
|000017e0| 20 4e 3d 4d 28 53 2b 78 | 5c 64 65 6c 74 61 20 53 | N=M(S+x|\delta S|
|000017f0| 29 24 0a 75 6e 74 69 6c | 20 74 68 65 20 66 69 72 |)$.until| the fir|
|00001800| 73 74 20 70 6f 73 69 74 | 69 76 69 74 79 20 63 6f |st posit|ivity co|
|00001810| 6e 73 74 72 61 69 6e 74 | 20 28 5c 72 65 66 7b 43 |nstraint| (\ref{C|
|00001820| 20 34 7d 29 20 69 73 20 | 68 69 74 2c 0a 74 68 65 | 4}) is |hit,.the|
|00001830| 6e 20 77 65 20 68 61 76 | 65 20 73 65 74 20 61 6e |n we hav|e set an|
|00001840| 20 65 78 74 72 61 20 24 | 74 24 20 76 61 72 69 61 | extra $|t$ varia|
|00001850| 62 6c 65 20 74 6f 20 7a | 65 72 6f 2c 20 61 6e 64 |ble to z|ero, and|
|00001860| 20 61 72 65 20 64 6f 6e | 65 2e 5d 0a 73 6f 20 74 | are don|e.].so t|
|00001870| 68 61 74 20 24 4d 5e 7b | 2d 31 7d 24 20 69 73 20 |hat $M^{|-1}$ is |
|00001880| 61 6c 73 6f 20 61 20 72 | 69 67 68 74 20 69 6e 76 |also a r|ight inv|
|00001890| 65 72 73 65 2e 20 57 65 | 20 63 61 6e 20 72 65 77 |erse. We| can rew|
|000018a0| 72 69 74 65 20 74 68 65 | 20 65 71 75 61 74 69 6f |rite the| equatio|
|000018b0| 6e 20 66 6f 72 20 24 53 | 24 0a 61 73 20 24 4e 20 |n for $S|$.as $N |
|000018c0| 3d 20 4d 5e 7b 2d 31 7d | 20 53 24 3b 20 6e 6f 77 |= M^{-1}| S$; now|
|000018d0| 20 62 79 20 63 6f 6e 74 | 69 6e 75 6f 75 73 6c 79 | by cont|inuously|
|000018e0| 20 6d 6f 64 69 66 79 69 | 6e 67 20 24 53 24 20 73 | modifyi|ng $S$ s|
|000018f0| 6f 20 61 73 20 74 6f 20 | 72 65 74 61 69 6e 0a 61 |o as to |retain.a|
|00001900| 6c 6c 20 74 68 65 20 7a | 65 72 6f 20 24 73 24 20 |ll the z|ero $s$ |
|00001910| 76 61 72 69 61 62 6c 65 | 73 20 6f 66 20 24 54 27 |variable|s of $T'|
|00001920| 24 2c 20 77 65 20 61 67 | 61 69 6e 20 67 65 74 20 |$, we ag|ain get |
|00001930| 73 6f 6c 75 74 69 6f 6e | 73 20 74 6f 0a 24 4c 50 |solution|s to.$LP|
|00001940| 24 20 28 62 79 20 63 6f | 6d 62 69 6e 69 6e 67 20 |$ (by co|mbining |
|00001950| 74 68 65 20 6d 6f 64 69 | 66 69 65 64 20 24 53 24 |the modi|fied $S$|
|00001960| 20 77 69 74 68 20 74 68 | 65 20 24 74 24 20 76 61 | with th|e $t$ va|
|00001970| 72 69 61 62 6c 65 73 20 | 6f 62 74 61 69 6e 65 64 |riables |obtained|
|00001980| 0a 62 79 20 63 6f 6d 70 | 75 74 69 6e 67 20 24 4e |.by comp|uting $N|
|00001990| 20 7e 3d 7e 20 4d 5e 7b | 2d 31 7d 20 53 24 20 77 | ~=~ M^{|-1} S$ w|
|000019a0| 68 69 63 68 20 6d 75 73 | 74 20 73 61 74 69 73 66 |hich mus|t satisf|
|000019b0| 79 20 24 4d 4e 3d 53 24 | 20 61 6e 64 20 6b 65 65 |y $MN=S$| and kee|
|000019c0| 70 69 6e 67 20 74 68 65 | 0a 72 65 6d 61 69 6e 69 |ping the|.remaini|
|000019d0| 6e 67 20 24 74 24 73 20 | 65 71 75 61 6c 20 74 6f |ng $t$s |equal to|
|000019e0| 20 24 30 24 29 0a 77 68 | 69 63 68 20 61 72 65 20 | $0$).wh|ich are |
|000019f0| 63 6f 76 65 72 65 64 20 | 62 79 20 24 54 27 24 20 |covered |by $T'$ |
|00001a00| 61 6e 64 20 65 76 65 6e | 74 75 61 6c 6c 79 20 77 |and even|tually w|
|00001a10| 65 20 67 65 74 20 6f 6e | 65 20 77 69 74 68 20 61 |e get on|e with a|
|00001a20| 6e 20 65 78 74 72 61 0a | 7a 65 72 6f 20 76 61 72 |n extra.|zero var|
|00001a30| 69 61 62 6c 65 2c 20 61 | 67 61 69 6e 20 63 6f 6e |iable, a|gain con|
|00001a40| 74 72 61 64 69 63 74 69 | 6e 67 20 74 68 65 20 64 |tradicti|ng the d|
|00001a50| 65 66 69 6e 69 74 69 6f | 6e 20 6f 66 20 24 54 27 |efinitio|n of $T'|
|00001a60| 24 2e 0a 0a 5b 54 68 65 | 20 66 6f 6c 6c 6f 77 69 |$...[The| followi|
|00001a70| 6e 67 20 61 72 67 75 6d | 65 6e 74 20 6f 66 20 4d |ng argum|ent of M|
|00001a80| 69 6b 65 27 73 20 69 73 | 20 6e 6f 6e 73 65 6e 73 |ike's is| nonsens|
|00001a90| 65 2c 20 62 65 63 61 75 | 73 65 20 68 65 20 64 6f |e, becau|se he do|
|00001aa0| 65 73 6e 27 74 0a 63 6f | 6e 73 69 64 65 72 20 77 |esn't.co|nsider w|
|00001ab0| 68 61 74 20 68 61 70 70 | 65 6e 73 20 74 6f 20 63 |hat happ|ens to c|
|00001ac0| 79 63 6c 65 73 20 63 6f | 6d 69 6e 67 20 6f 66 66 |ycles co|ming off|
|00001ad0| 20 74 68 65 20 6d 61 69 | 6e 20 63 79 63 6c 65 5d | the mai|n cycle]|
|00001ae0| 0a 7b 54 6f 20 73 65 65 | 20 74 68 61 74 20 74 68 |.{To see| that th|
|00001af0| 65 20 24 73 24 20 76 61 | 72 69 61 62 6c 65 73 20 |e $s$ va|riables |
|00001b00| 63 61 6e 20 69 6e 64 65 | 65 64 20 62 65 20 6d 6f |can inde|ed be mo|
|00001b10| 64 69 66 69 65 64 20 69 | 6e 20 74 68 69 73 20 77 |dified i|n this w|
|00001b20| 61 79 2c 0a 63 6f 6e 73 | 69 64 65 72 20 74 68 65 |ay,.cons|ider the|
|00001b30| 20 24 73 24 20 76 61 72 | 69 61 62 6c 65 73 20 77 | $s$ var|iables w|
|00001b40| 68 69 63 68 20 61 72 65 | 20 6e 65 69 74 68 65 72 |hich are| neither|
|00001b50| 20 24 30 24 20 6e 6f 72 | 20 24 31 24 3b 0a 61 6e | $0$ nor| $1$;.an|
|00001b60| 79 20 73 75 63 68 20 24 | 73 5f 7b 61 2c 62 7d 24 |y such $|s_{a,b}$|
|00001b70| 20 6d 75 73 74 20 68 61 | 76 65 20 61 74 20 6c 65 | must ha|ve at le|
|00001b80| 61 73 74 20 6f 6e 65 20 | 6d 61 74 63 68 69 6e 67 |ast one |matching|
|00001b90| 20 24 20 73 5f 7b 61 27 | 20 2c 62 7d 24 0a 61 6e | $ s_{a'| ,b}$.an|
|00001ba0| 64 20 6f 6e 65 20 24 20 | 73 5f 7b 61 2c 20 62 27 |d one $ |s_{a, b'|
|00001bb0| 7d 24 3b 20 6a 6f 69 6e | 20 74 68 65 73 65 20 74 |}$; join| these t|
|00001bc0| 6f 0a 24 73 5f 7b 61 2c | 62 7d 24 20 62 79 20 65 |o.$s_{a,|b}$ by e|
|00001bd0| 64 67 65 73 20 74 6f 20 | 67 69 76 65 20 61 20 67 |dges to |give a g|
|00001be0| 72 61 70 68 20 24 47 24 | 3b 0a 24 47 24 20 6d 75 |raph $G$|;.$G$ mu|
|00001bf0| 73 74 20 63 6f 6e 74 61 | 69 6e 20 61 20 63 79 63 |st conta|in a cyc|
|00001c00| 6c 65 20 77 69 74 68 20 | 61 6c 74 65 72 6e 61 74 |le with |alternat|
|00001c10| 69 6e 67 20 60 68 6f 72 | 69 7a 6f 6e 74 61 6c 27 |ing `hor|izontal'|
|00001c20| 20 61 6e 64 20 60 76 65 | 72 74 69 63 61 6c 27 0a | and `ve|rtical'.|
|00001c30| 65 64 67 65 73 3b 20 61 | 64 64 20 24 5c 65 70 73 |edges; a|dd $\eps|
|00001c40| 69 6c 6f 6e 24 20 6f 72 | 20 24 2d 5c 65 70 73 69 |ilon$ or| $-\epsi|
|00001c50| 6c 6f 6e 24 20 74 6f 20 | 74 68 65 20 76 65 72 74 |lon$ to |the vert|
|00001c60| 69 63 65 73 20 61 6c 6f | 6e 67 20 74 68 69 73 20 |ices alo|ng this |
|00001c70| 63 79 63 6c 65 0a 61 6c | 74 65 72 6e 61 74 65 6c |cycle.al|ternatel|
|00001c80| 79 20 74 6f 20 6d 6f 64 | 69 66 79 20 74 68 65 20 |y to mod|ify the |
|00001c90| 24 73 24 20 76 61 72 69 | 61 62 6c 65 73 20 69 6e |$s$ vari|ables in|
|00001ca0| 20 74 68 65 20 72 65 71 | 75 69 72 65 64 20 77 61 | the req|uired wa|
|00001cb0| 79 2e 7d 0a 0a 5c 62 69 | 67 73 6b 69 70 0a 4e 6f |y.}..\bi|gskip.No|
|00001cc0| 77 20 77 65 20 72 65 67 | 61 72 64 20 74 68 65 20 |w we reg|ard the |
|00001cd0| 76 61 72 69 61 62 6c 65 | 73 20 24 74 24 20 61 73 |variable|s $t$ as|
|00001ce0| 20 63 6f 6e 73 74 69 74 | 75 74 69 6e 67 20 61 20 | constit|uting a |
|00001cf0| 73 71 75 61 72 65 20 6d | 61 74 72 69 78 0a 77 69 |square m|atrix.wi|
|00001d00| 74 68 20 73 75 62 73 63 | 72 69 70 74 73 20 74 61 |th subsc|ripts ta|
|00001d10| 6b 65 6e 20 66 72 6f 6d | 20 74 68 65 20 70 61 69 |ken from| the pai|
|00001d20| 72 73 20 24 61 2c 63 24 | 20 28 24 61 20 5c 6e 65 |rs $a,c$| ($a \ne|
|00001d30| 20 63 24 29 20 6f 72 20 | 24 62 2c 64 24 20 77 69 | c$) or |$b,d$ wi|
|00001d40| 74 68 20 24 62 20 5c 6e | 65 20 64 24 2e 0a 0a 5c |th $b \n|e d$...\|
|00001d50| 62 69 67 73 6b 69 70 5c | 6e 6f 69 6e 64 65 6e 74 |bigskip\|noindent|
|00001d60| 0a 43 6c 61 69 6d 20 33 | 3a 20 49 66 20 54 20 69 |.Claim 3|: If T i|
|00001d70| 73 20 61 20 73 6f 6c 75 | 74 69 6f 6e 20 74 6f 20 |s a solu|tion to |
|00001d80| 24 4c 50 24 20 61 6e 64 | 20 63 6f 76 65 72 73 20 |$LP$ and| covers |
|00001d90| 61 20 70 65 72 6d 75 74 | 61 74 69 6f 6e 20 76 65 |a permut|ation ve|
|00001da0| 63 74 6f 72 0a 24 51 24 | 2c 20 61 6e 64 20 24 41 |ctor.$Q$|, and $A|
|00001db0| 24 20 61 6e 64 20 24 42 | 24 20 61 72 65 0a 76 65 |$ and $B|$ are.ve|
|00001dc0| 63 74 6f 72 73 20 77 69 | 74 68 20 61 6c 6c 20 65 |ctors wi|th all e|
|00001dd0| 6c 65 6d 65 6e 74 73 20 | 24 30 24 20 6f 72 20 24 |lements |$0$ or $|
|00001de0| 31 24 2c 20 69 66 20 24 | 54 41 3d 42 24 20 74 68 |1$, if $|TA=B$ th|
|00001df0| 65 6e 20 24 51 41 3d 42 | 24 2e 0a 0a 5c 62 69 67 |en $QA=B|$...\big|
|00001e00| 73 6b 69 70 5c 6e 6f 69 | 6e 64 65 6e 74 0a 50 72 |skip\noi|ndent.Pr|
|00001e10| 6f 6f 66 3a 20 43 6f 6e | 73 69 64 65 72 20 61 6e |oof: Con|sider an|
|00001e20| 20 65 6c 65 6d 65 6e 74 | 20 24 42 5f 69 24 20 6f | element| $B_i$ o|
|00001e30| 66 20 24 42 24 20 61 6e | 64 20 6e 6f 74 65 20 74 |f $B$ an|d note t|
|00001e40| 68 61 74 20 24 42 5f 69 | 20 3d 20 54 5f 69 20 41 |hat $B_i| = T_i A|
|00001e50| 24 0a 28 77 68 65 72 65 | 20 24 54 5f 69 24 20 69 |$.(where| $T_i$ i|
|00001e60| 73 20 74 68 65 20 24 69 | 24 74 68 20 72 6f 77 20 |s the $i|$th row |
|00001e70| 6f 66 20 24 54 24 2c 20 | 6e 61 6d 65 6c 79 20 61 |of $T$, |namely a|
|00001e80| 20 76 65 63 74 6f 72 20 | 77 69 74 68 0a 6e 6f 6e | vector |with.non|
|00001e90| 2d 6e 65 67 61 74 69 76 | 65 20 65 6c 65 6d 65 6e |-negativ|e elemen|
|00001ea0| 74 73 20 77 68 6f 73 65 | 20 73 75 6d 20 69 73 20 |ts whose| sum is |
|00001eb0| 24 31 24 29 2e 0a 49 66 | 20 24 42 5f 69 20 3d 30 |$1$)..If| $B_i =0|
|00001ec0| 24 2c 20 74 68 65 6e 20 | 24 54 5f 69 20 41 20 3d |$, then |$T_i A =|
|00001ed0| 30 24 20 61 6e 64 20 63 | 6c 65 61 72 6c 79 20 61 |0$ and c|learly a|
|00001ee0| 6c 73 6f 20 24 51 5f 69 | 20 41 20 3d 30 24 20 61 |lso $Q_i| A =0$ a|
|00001ef0| 6c 73 6f 0a 73 69 6e 63 | 65 20 74 68 65 20 70 6f |lso.sinc|e the po|
|00001f00| 73 69 74 69 76 65 20 65 | 6c 65 6d 65 6e 74 73 20 |sitive e|lements |
|00001f10| 6f 66 20 24 51 5f 69 24 | 20 61 72 65 20 61 20 73 |of $Q_i$| are a s|
|00001f20| 75 62 73 65 74 20 6f 66 | 20 74 68 6f 73 65 20 6f |ubset of| those o|
|00001f30| 66 20 24 41 5f 69 24 2e | 0a 49 66 20 24 42 5f 69 |f $A_i$.|.If $B_i|
|00001f40| 20 3d 20 31 24 2c 20 54 | 68 65 6e 20 24 41 24 20 | = 1$, T|hen $A$ |
|00001f50| 6d 75 73 74 20 68 61 76 | 65 20 65 6c 65 6d 65 6e |must hav|e elemen|
|00001f60| 74 20 24 41 5f 6a 24 20 | 65 71 75 61 6c 20 74 6f |t $A_j$ |equal to|
|00001f70| 20 24 31 24 20 77 68 65 | 72 65 76 65 72 0a 24 54 | $1$ whe|rever.$T|
|00001f80| 5f 7b 69 2c 6a 7d 24 20 | 69 73 20 6e 6f 6e 7a 65 |_{i,j}$ |is nonze|
|00001f90| 72 6f 3b 20 62 75 74 20 | 24 51 5f 69 24 20 68 61 |ro; but |$Q_i$ ha|
|00001fa0| 73 20 65 78 61 63 74 6c | 79 20 6f 6e 65 20 6e 6f |s exactl|y one no|
|00001fb0| 6e 7a 65 72 6f 20 65 6c | 65 6d 65 6e 74 2c 20 61 |nzero el|ement, a|
|00001fc0| 0a 24 51 5f 7b 69 2c 6a | 7d 24 20 77 68 69 63 68 |.$Q_{i,j|}$ which|
|00001fd0| 20 69 73 20 65 71 75 61 | 6c 20 74 6f 20 24 31 24 | is equa|l to $1$|
|00001fe0| 20 66 6f 72 20 61 20 24 | 6a 24 20 73 75 63 68 20 | for a $|j$ such |
|00001ff0| 74 68 61 74 20 24 54 5f | 7b 69 2c 6a 7d 24 20 69 |that $T_|{i,j}$ i|
|00002000| 73 0a 70 6f 73 69 74 69 | 76 65 3b 20 68 65 6e 63 |s.positi|ve; henc|
|00002010| 65 20 24 20 51 5f 69 20 | 41 20 3d 20 31 24 2e 0a |e $ Q_i |A = 1$..|
|00002020| 0a 0a 5c 62 69 67 73 6b | 69 70 5c 6e 6f 69 6e 64 |..\bigsk|ip\noind|
|00002030| 65 6e 74 0a 52 65 6d 61 | 72 6b 3a 20 54 68 65 20 |ent.Rema|rk: The |
|00002040| 73 61 6d 65 20 61 6e 61 | 6c 79 73 69 73 20 68 6f |same ana|lysis ho|
|00002050| 6c 64 73 20 69 66 20 77 | 65 20 72 65 73 74 72 69 |lds if w|e restri|
|00002060| 63 74 20 6f 75 72 20 61 | 74 74 65 6e 74 69 6f 6e |ct our a|ttention|
|00002070| 20 74 6f 20 74 77 6f 0a | 73 75 62 6d 61 74 72 69 | to two.|submatri|
|00002080| 63 65 73 20 24 5c 74 69 | 6c 64 65 7b 54 7d 24 20 |ces $\ti|lde{T}$ |
|00002090| 61 6e 64 20 24 5c 74 69 | 6c 64 65 7b 51 7d 24 20 |and $\ti|lde{Q}$ |
|000020a0| 6f 62 74 61 69 6e 65 64 | 20 62 79 20 64 65 6c 65 |obtained| by dele|
|000020b0| 74 69 6e 67 20 63 65 72 | 74 61 69 6e 20 72 6f 77 |ting cer|tain row|
|000020c0| 73 0a 66 72 6f 6d 20 62 | 6f 74 68 20 24 54 24 20 |s.from b|oth $T$ |
|000020d0| 61 6e 64 20 24 51 24 2e | 0a 0a 5c 62 69 67 73 6b |and $Q$.|..\bigsk|
|000020e0| 69 70 5c 6e 6f 69 6e 64 | 65 6e 74 0a 43 6f 72 6f |ip\noind|ent.Coro|
|000020f0| 6c 6c 61 72 79 3a 20 48 | 61 6d 69 6c 74 6f 6e 69 |llary: H|amiltoni|
|00002100| 61 6e 20 43 69 72 63 75 | 69 74 20 69 73 20 69 6e |an Circu|it is in|
|00002110| 20 24 50 24 2e 0a 0a 5c | 62 69 67 73 6b 69 70 5c | $P$...\|bigskip\|
|00002120| 6e 6f 69 6e 64 65 6e 74 | 0a 50 72 6f 6f 66 3a 20 |noindent|.Proof: |
|00002130| 41 73 20 69 6e 20 5b 47 | 69 73 6d 6f 6e 64 69 20 |As in [G|ismondi |
|00002140| 61 6e 64 20 53 77 61 72 | 74 5d 2e 0a 0a 5c 62 69 |and Swar|t]...\bi|
|00002150| 67 73 6b 69 70 5c 6e 6f | 69 6e 64 65 6e 74 0a 54 |gskip\no|indent.T|
|00002160| 68 65 6f 72 65 6d 3a 20 | 50 3d 4e 50 2e 0a 0a 5c |heorem: |P=NP...\|
|00002170| 62 69 67 73 6b 69 70 5c | 6e 6f 69 6e 64 65 6e 74 |bigskip\|noindent|
|00002180| 0a 52 65 6d 61 72 6b 3a | 20 54 68 69 73 20 70 72 |.Remark:| This pr|
|00002190| 6f 76 65 73 20 74 68 61 | 74 20 74 68 65 20 76 61 |oves tha|t the va|
|000021a0| 72 69 6f 75 73 20 47 69 | 73 6d 6f 6e 64 69 20 61 |rious Gi|smondi a|
|000021b0| 6e 64 20 53 77 61 72 74 | 20 61 6c 67 6f 72 69 74 |nd Swart| algorit|
|000021c0| 68 6d 73 20 61 72 65 0a | 63 6f 72 72 65 63 74 20 |hms are.|correct |
|000021d0| 73 69 6e 63 65 20 74 68 | 65 69 72 20 73 65 74 73 |since th|eir sets|
|000021e0| 20 6f 66 20 63 6f 6e 73 | 74 72 61 69 6e 74 73 20 | of cons|traints |
|000021f0| 61 72 65 20 73 75 70 65 | 72 73 65 74 73 20 6f 66 |are supe|rsets of|
|00002200| 20 74 68 65 20 6f 6e 65 | 73 0a 75 73 65 64 20 68 | the one|s.used h|
|00002210| 65 72 65 20 61 6e 64 20 | 61 72 65 20 63 65 72 74 |ere and |are cert|
|00002220| 61 69 6e 6c 79 20 73 61 | 74 69 73 66 69 65 64 20 |ainly sa|tisfied |
|00002230| 62 79 20 74 68 65 20 70 | 65 72 6d 75 74 61 74 69 |by the p|ermutati|
|00002240| 6f 6e 20 76 65 63 74 6f | 72 73 2e 0a 49 20 63 6c |on vecto|rs..I cl|
|00002250| 61 69 6d 20 74 68 61 74 | 20 74 68 69 73 20 69 73 |aim that| this is|
|00002260| 20 74 68 65 20 66 69 72 | 73 74 20 76 61 6c 69 64 | the fir|st valid|
|00002270| 20 70 72 6f 6f 66 20 6f | 66 20 50 3d 4e 50 20 61 | proof o|f P=NP a|
|00002280| 6e 64 20 74 68 61 74 20 | 74 68 65 0a 61 6c 67 6f |nd that |the.algo|
|00002290| 72 69 74 68 6d 73 20 69 | 6d 70 6c 69 65 64 20 62 |rithms i|mplied b|
|000022a0| 79 20 74 68 69 73 20 70 | 72 6f 6f 66 20 61 72 65 |y this p|roof are|
|000022b0| 20 6d 75 63 68 20 73 69 | 6d 70 6c 65 72 20 74 68 | much si|mpler th|
|000022c0| 61 6e 20 74 68 65 69 72 | 73 2e 0a 0a 5c 65 6e 64 |an their|s...\end|
|000022d0| 7b 64 6f 63 75 6d 65 6e | 74 7d 0a                |{documen|t}.     |
+--------+-------------------------+-------------------------+--------+--------+