Изменения

{{Лемма

|statement=<tex>LSAT \in NPC</tex>.

|proof=

{{Лемма

|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT</tex>.

|proof=<tex>\langle\phi,y\rangle \in LSAT</tex>. Тогда <tex>\exists x: x<_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in LSAT</tex>.