Discuție:Problema clicii

	Articolul Problema clicii este un subiect de care se ocupă Proiectul Informatică, o inițiativă de a construi o listă cuprinzătoare și detaliată cu informații despre Informatică Dacă doriți să participați la acest proiect, vă rugăm să vă înscrieți aici.
B	Acest articol a fost evaluat ca făcând parte din grupa B pe scala de calitate.
Neclasificat	Acest articol încă nu a fost evaluat pe scala de importanță.

Includere in categoria Teoria grafurilor

Ține acest subiect doar de informatică sau și de teoria grafurilor unde este si categorizat?--5.2.200.163 (discuție) 28 august 2017 15:44 (EEST)

Wp germană zice explicit: Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Ar trebuie luată in considerare acaeasta precizare de pe dewp. Un articol similar de pe rowp teoria computației precizează o includere in informatica teoretică pe langă matematică.

Asadar revenirile care exclud din introducere includerea in teoria grafurilor sunt nejustificate.--5.2.200.163 (discuție) 28 august 2017 15:49 (EEST)

Ține, dar e oarecum tangențial. În definiția ei cea mai utilizată, este exprimată în termeni de noțiuni de teoria grafurilor, dar problema în sine e una computațională, de algoritmică (și deci de informatică) — anume, găsirea unui algoritm care să aibă o anume complexitate și care să rezolve problema pe orice caz; se poate chiar enunța în termeni de concepte diferite (de exemplu, de permutări sau logică booleană).

O problemă care chiar este în definiția ei de teoria grafurilor e, de exemplu, demonstrarea că un arbore cu n noduri are n−1 muchii. Ea nu presupune dezvoltare de algoritmi, complexități și alte asemenea, ci strict calcule și demonstrații de teoria grafurilor.

Articolul e o traducere din en.wp (nu de.wp), unde (în mod corect, zic eu) nu este definită din prima frază ca problemă de teoria grafurilor, ci de informatică; și doar enunțată în termeni de teoria grafurilor.  —Andrei^discuție 28 august 2017 16:05 (EEST)

PS: Nu prea știu germană, dar știu că Entscheidungsproblem înseamnă problemă a deciziei, concept care oricum este asociat direct informaticii și teoriei computației. În acest sens, am putea-o defini și așa, doar că definiția ar fi mai limitată decât este sfera de interes a articolului. Forma problemei clicii ca problemă a deciziei este doar una din formele în care poate apărea („să se determine dacă în graful G există o k-clică”), dar articolul tratează și celelalte forme, în special cea de bază („să se enumere clicile maxime ale grafului G”). —Andrei^discuție 28 august 2017 16:14 (EEST)

Care sunt dpdv computational (dar si de includere in matematica grafurilor) asemănările (și deosebirile) problemei clicii cu problema comis-voiajorului? S-ar parea ca similar, pcv e o problema legată de grafuri, dar rezolvarea ei se reduce la gasirea unui algoritm eficient contra exploziei combinatorice cand valoarea de intrare a funcției numerice discrete factorial este mare(>11-15)?--5.2.200.163 (discuție) 29 august 2017 15:31 (EEST)

Computațional, cam toate problemele sunt așa: rezolvarea lor înseamnă găsirea unui algoritm cu o eficiență asimptotică ce le plasează într-o clasă sau alta de complexitate. Din acest punct de vedere, asemănarea între ele este chiar puțin mai mare decât atât: ambele sunt NP-complete, adică se reduc una la cealaltă în timp polinomial, dar în același timp ele însele sunt din clasa de complexitate NP. Complexitatea algoritmilor care le rezolvă diferă în mare parte prin amănunte — altă bază a exponențialei, diferențe la termenii polinomiali.

Dacă ne uităm la conceptele de teoria grafurilor pe care le explorează, diferă puțin conceptul pe care se sprijină: drumul/ciclul hamiltonian la PCV și subgraful complet la problema clicii și deci și domeniile de aplicabilitate ale soluțiilor; diferențele astea produc unele mici scurtături matematice ce pot fi exploatate ca optimizări, optimizări care duc la acele diferențe mici de complexitate a algoritmilor care le rezolvă. Privind lucrurile așa, e destul de intuitiv de ce se reduc una la alta. —Andrei^discuție 30 august 2017 10:05 (EEST)