ՀՀ ԳԱԱ Զեկույցներ =Reports NAS RA

О NP-полноте "СВЯЗНОЙ 3-ВЫПОЛНИМОСТИ"

Мкртчян, В. В. and Камалян, Р. Р. (2003) О NP-полноте "СВЯЗНОЙ 3-ВЫПОЛНИМОСТИ". ՀՀ ԳԱԱ Զեկույցներ, 103 (2). pp. 105-108. ISSN 0321-1339

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
128Kb

Abstract

Աշխատանքում ապացուցված է «3-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅՈՒՆ» խնդրի մի մասնավոր դեպքի NP-լրիվությունը, որում կամայական երկու փոփոխականների համար գոյություն ունի փոփոխականների այնպիսի հաջորդականություն, որը սկսվում է նրանցից մեկով, ավարտվում` մյուսով և որի ցանկացած երկու հարևան փոփոխականների համար գոյություն ունի այդ փոփոխականների լիտերալները պարունակող դիզյունկցիա:

Item Type:Article
Additional Information:«ԿԱՊԱԿՑՎԱԾ 3-ԻՐԱԳՈՐԾԵԼԻՈՒԹՅԱՆ» NP-լրիվության մասին։ “Connected 3-Satisfiability” is NP-complete.
Uncontrolled Keywords:Մկրտչյան Վ. Վ., Քամալյան Ռ. Ռ., Mkrtchyan M. V., Kamalian R.R.
Subjects:Q Science > QA Mathematics
ID Code:725
Deposited By:NAS Reports
Deposited On:20 Jul 2011 14:08
Last Modified:13 Mar 2014 08:17

Repository Staff Only: item control page