Լուծելիության պրոբլեմ
From Wikipedia, the free encyclopedia
Լուծելիության պրոբլեմ, զանգվածային պրոբլեմների կարևոր տեսակ։ Կոնստրուկտիվ օբյեկտների որևէ A դասի Լուծելիության պրոբլեմը ավելի ընդհանուր է B դասի նկատմամբ այնպիսի ալգորիթմի կառուցման պրոբլեմն է, որը հնարավորություն է տալիս A-ի ցանկացած տարրի համար պարզելու՝ պատկանո՞ւմ է արդյոք այն B-ին, թե՝ ոչ։ Ձևական համակարգերի ապացուցելիության համար Լուծելիության պրոբլեմ կոչվում է համակարգում ապացուցվող բանաձևերի դասի Լուծելիության պրոբլեմ համակարգի բոլոր բանաձեվերի նկատմամբ։ Այստեղ Լուծելիության պրոբլեմը կապվում է այնպիսի մեթոդի գոյության (կամ չգոյության) հետ, որը հնարավորություն կտա վերջավոր թվով քայլերի միջոցով պարզելու՝ քննարկվող համակարգի որևէ բանաձև արդյո՞ք ապացուցելի (ճշմարիտ) է տվյալ համակարգում, թե՝ այդպիսին չէ։ Այս ըմբռնմամբ Լուծելիության պրոբլեմը դրականորեն է լուծվում ասույթների հաշվում և ձևականացված արիստոտելյան սիլլոգիստիկայում։ Այն հայտնի է նաև Չյորչի թեորեմ[1]։