Llista de problemes 4

Intruccions

Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:

Vídeos de Sipser

• Lecture 12: Time Complexity
• Lecture 13: P and NP, SAT, poly-time reducibility
• Lecture 15: NP-completeness

Llibres

• (Sipser 2013, \S 7)
• (Hopcroft, Motwani, i Ullman 2007, \S 10 and \S 11.1)

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.

Tots els exercicis

Exercici 1 (Problema del viatjant de comerç) Suposem que se’ns dona una instància del Problema del Viatjant de Comerç (\mathtt{TSP}) amb n ciutats i distàncies d_{ij}. Per a cada subconjunt S de les ciutats excloent la ciutat 1, i per a cada j \in S, definim c[S,j] com el camí més curt que comença a la ciutat 1, visita totes les ciutats de S i acaba a la ciutat j.

1. Doneu un algorisme que calculi c[S,j] mitjançant programació dinàmica, és a dir, progressant de conjunts S més petits a conjunts més grans i utilitzant una definició recurrent de c[S,j]. Mostreu que aquest algoritme resol el \mathtt{TSP} en temps O(n^2 2^n). Quins són els requeriments d’espai de l’algoritme?

2. Suposem que volem trobar el camí més curt (en el sentit de la suma dels pesos) de 1 a n, sense necessitat de visitar totes les ciutats. Argumenteu per què aquest problema es pot resoldre en temps polinòmic.

Exercici 2 (A la recerca de cliques) Una k-clica en un graf G = (V,E) és un subgraf complet d’ordre k de G, és a dir, un subgraf de k vèrtexs que conté totes les arestes possibles entre ells. Diem que G' és una clica en G si G' és una k-clica en G per a algun k. Recordeu que el problema següent és un NP-complet conegut. \mathtt{Clica}\text{: Donat un graf no dirigit $G$ i un natural $k$, determinar si $G$ conté una $k$-clica.}

Els següents són alguns problemes relacionats amb \mathtt{Clica}.

1. Clica maximal. Una clica és maximal si no es pot estendre, és a dir, si no hi ha cap clica més gran que la contingui. Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica maximal de G. Quin és el cost de l’algorisme?

2. Clica màxima. Una clica és màxima si no hi ha cap altra clica que tingui més vèrtexs (una clica màxima sempre és maximal però la inclusió inversa no sempre és certa). Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica màxima de G. Quin és el cost de l’algorisme?

3. Clica planar. Recordeu que un graf és planar si es pot dibuixar en el pla sense creuaments d’arestes. Sigui \mathtt{Clica Planar} el problema següent: donat un graf planar no dirigit G i un natural k, té G una k-clica? Demostreu que \mathtt{Clica Planar} té un algorisme de temps polinòmic.

   Nota

   La comprovació de la planaritat es pot fer en temps lineal (en el nombre de vèrtexs). Podeu assumir l’existència d’aquests algorismes per l’exercici.

4. Mitja clica. Sigui \mathtt{Mitja Clica} el problema següent: donat un graf no dirigit G, té G una clica amb almenys \big\lceil \frac{|V(G)|}{2} \big\rceil vèrtexs? Demostreu que \mathtt{Mitja Clica} és \mathbf{NP}-complet.

Exercici 3 (Propietats de tancament de \mathbf{P}, \mathbf{NP} i \mathbf{coNP}) L’objectiu d’aquest exercici és revisar algunes propietats de tancament de \mathbf{P}, \mathbf{NP} i \mathbf{coNP}.

1. (propietat de tancament respecte de la unió) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cup B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cup B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cup B\in \mathbf{coNP}.
2. (propietat de tancament respecte de la intersecció) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cap B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cap B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cap B\in \mathbf{coNP}.
3. (propietat de tancament respecte de la concatenació) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cdot B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cdot B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cdot B\in \mathbf{coNP}.

Exercici 4 (Reduccions de temps polinòmic) Considereu la relació \le_m^p entre llenguatges i justifiqueu les respostes a les preguntes següents.

1. És \le_m^p reflexiva? És a dir, es compleix que A \le_m^p A per a qualsevol llenguatge A?

2. És \le_m^p simètrica? És a dir, es compleix que si A \le_m^p B, aleshores B \le_m^p A per a qualssevol llenguatges A, B?

3. És \le_m^p antisimètrica? És a dir, es compleix que A \le_m^p B i B \le_m^p A impliquen A = B per a qualssevol llenguatges A, B?

4. És \le_m^p transitiva? És a dir, es compleix que A \le_m^p B i B \le_m^p C impliquen A \le_m^p C per a qualssevol llenguatges A, B i C?

Reduccions polinomiques \leq_m^p

Recordeu que, donats dos llenguatges A, B sobre el mateix alfabet \Sigma, diem que A es redueix polinòmicamente a B (s’escriu A\leq_m^p B o A \leq_p B) si existeix una funció total f:\Sigma^*\to\Sigma^* computable en temps polinòmic tal que per a tot w\in \Sigma^*, w\in A si i només si f(w)\in B.

Una propietat útil és el tancament de les classes \mathbf{P}, \mathbf{NP} i \mathbf{coNP} per reduccions polinòmiques, és a dir, donat A\leq_m^p B,

• si B\in \mathbf{P}, llavors A\in \mathbf{P},
• si B\in \mathbf{NP}, llavors A\in \mathbf{NP}, i
• si B\in \mathbf{coNP}, llavors A\in \mathbf{coNP}.

La m en la notació \leq_m^p indica que la funció f no és necessàriament injectiva (és many-one).

Exercici 5 (Tancament per l’estrella de Kleene)  

1. Mostreu que \mathbf{P} és tancada per l’estrella de Kleene.

   Consell

   Utilitzeu programació dinàmica. Donat un conjunt A \in \mathbf{P} sobre \Sigma i una entrada x = x_1 \dots x_n amb x_i \in \Sigma, construïu una taula que indiqui per a cada i < j si el submot x_i \dots x_j és a A^*.

2. Mostreu que \mathbf{NP} és tancada per l’estrella de Kleene.

Exercici 6 (Cerca vs decisió) Demostreu les conseqüències següents de la hipòtesi \mathbf{P} = \mathbf{NP}.

1. Existeix un algorisme de temps polinòmic que produeix un model (una assignació que satisfà la fórmula) quan se li dóna una fórmula booleana satisfactible.

2. Els enters es poden factoritzar en temps polinòmic.

3. Hi ha un algorisme de temps polinòmic que pren com a entrada un graf no dirigit i troba una clica màxima (vegeu l’exercici 7.2) continguda en aquest graf.

Nota

Els algorismes que se us demana proporcionar calculen una funció, però \mathbf{NP} conté llenguatges, no funcions. L’assumpció \mathbf{P} = \mathbf{NP} implica que decidir satisfactibilitat, no primalitat i l’existència de cliques d’una mida donada és resoluble en temps polinòmic. Però, encara que l’assumpció no mostra com trobar les solucions, heu de demostrar que es poden trobar igualment.

Exercici 7 (Teorema de Berman) Un llenguatge s’anomena unari si cada mot que conté és de la forma 1^n per a algun n \ge 0.

Demostreu el teorema de Berman (1978): si un llenguatge unari és \mathbf{NP}-complet, aleshores \mathbf{P} = \mathbf{NP}.

Consell

Utilitzeu el fet que \mathtt{SAT} és \mathbf{NP}-complet i, per hipòtesi, reductible a un llenguatge unari mitjançant una funció f. Per decidir \mathtt{SAT}, donada una fórmula booleana d’entrada \phi, considereu l’arbre on l’arrel (nivell 0) és \phi i les fórmules al nivell k s’obtenen de les del nivell k-1 de manera que la k-èsima variable pren els 2 valors de veritat possibles. Demostreu com f permet explorar aquest arbre en temps polòmic.

Exercici 8 (\mathbf{NP} i \mathtt{HALT}) Demostreu que \mathtt{HALT} és \mathbf{NP}-difícil. És també \mathbf{NP}-complet?

Nota

Recordeu que \mathtt{HALT}=\{\langle x,y \rangle \mid M_x(y)\!\downarrow\}\ , on M_x és la màquina de Turing amb nombre de Gödel x i el símbol \downarrow indica que la màquina finalitza.

Exercici 9 (\mathtt{UniqueSAT}) La classe \mathbf{DP} (de difference polynomial time) es defineix com el conjunt de llenguatges L per als quals existeixen dos llenguatges L_1 \in \mathbf{NP}, L_2 \in \mathbf{coNP} tals que L = L_1 \cap L_2. Cal notar que, com que \overline{L_2} \in \mathbf{NP}, L és la diferència de dos conjunts de \mathbf{NP} (però no confongueu \mathbf{DP} amb \mathbf{NP} \cap \mathbf{coNP}, que s’assembla superficialment).

Considereu el problema \mathtt{Unique SAT}, que consisteix a determinar si una fórmula booleana té una única assignació satisfactible (o model) i demostreu els següents fets.

1. \mathtt{Unique SAT} \in \mathbf{DP}.
   
2. Si \mathtt{Unique SAT} és a \mathbf{NP}, aleshores \mathbf{NP} = \mathbf{coNP}.

Exercici 10 (Pertanyen a \mathbf{P}?) Demostreu que els llenguatges següents sobre grafs no dirigits són a \mathbf{NP}. Quins pertanyen a \mathbf{P}?

1. Dos coloració. \mathtt{2COL} = \{ G \mid el graf G té una 2-coloració\}, on una k-coloració de G és una assignació d’un nombre a \{1,\dots,k\} a cada vèrtex de G tal que tot parell de vèrtexs adjacents rep colors diferents.
2. Tres coloració. \mathtt{3COL} = \{ G \mid el graf G té una 3-coloració\}.
3. Camí hamiltonià. \mathtt{HP} = \{ G \mid el graf G té un camí hamiltonià\}, on un camí se’n diu hamiltonià si visita cada vèrtex exactament un cop.
4. Connectivitat. \mathtt{CONNECTED} =\{ G \mid G és un graf connex\}.