Լուծելիության պրոբլեմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

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

Այս հոդվածի կամ նրա բաժնի որոշակի հատվածի սկզբնական կամ ներկայիս տարբերակը վերցված է Քրիեյթիվ Քոմմոնս Նշում–Համանման տարածում 3.0 (Creative Commons BY-SA 3.0) ազատ թույլատրագրով թողարկված Հայկական սովետական հանրագիտարանից  (հ․ 4, էջ 677 CC-BY-SA-icon-80x15.png