67321

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Доклад

Название: 

About strong dependence of the complexity of analysis of the random 3-cnf formulas on the ratio of number of clauses to the number of variables

ISBN/ISSN: 

0922-6389 978-1-64368-224-2 (print) | 978-1-64368-225-9 (online)

DOI: 

10.3233/FAIA210281

Наименование конференции: 

  • 3th International Conference on Machine Learning and Intelligent Systems (MLIS 2021, China)

Наименование источника: 

  • Frontiers in Artificial Intelligence and Applications

Обозначение и номер тома: 

Vol. 341

Город: 

  • Beijing, China

Издательство: 

  • IOS Press.

Год издания: 

2021

Страницы: 

496-501
Аннотация
The results of a computational experiment on the assessment of the complexity of proving the unsatisfiability of random 3-CNF logical formulas are presented. The dependence of the complexity of this proving on the R-ratio of the number of clauses to the number of variables is demonstrated. The computational experiment was carried out for the range of the N-number of variables from 256 to 512. An exponential dependence of the median complexity of proving the unsatisfiability of formulas on the number of variables was revealed for each of R value: 4.3, 4.6, 5.0, 5.5, 6.0. A formula is constructed that approximates the results of the experiment. According to this formula the exponential component of the median complexity of the analysis of random 3-CNF is estimated as 2 to the power N / (8.4R-17.8).

Библиографическая ссылка: 

Уваров С.И. About strong dependence of the complexity of analysis of the random 3-cnf formulas on the ratio of number of clauses to the number of variables / Frontiers in Artificial Intelligence and Applications. Beijing, China: IOS Press., 2021. Vol. 341. С. 496-501.