首页 | 本学科首页   官方微博 | 高级检索  
     检索      


<Emphasis Type="Italic">NP</Emphasis> completeness conditions for verifying the consistency of several kinds of systems of linear diophantine discongruences
Authors:N K Kosovskii  T M Kosovskaya  N N Kosovskii
Abstract:We propose two series of number-theory problems with explicitly marked out parameters related to discongruences modulo m. We find parameter constraints that provide the NP completeness for any problem of every series. For any m > 2, we prove the NP completeness of the verification problem for the consistency of a system of linear discongruences modulo m such that any discongruence contains exactly three variables, including the case where its coefficients belong to {–1, 1}. For any m > 3, we prove the NP completeness of the verification problem for the consistency of a system of linear discongruences modulo m such that any discongruence contains exactly 2 variables. If P ≠ NP, then one cannot change the term 2-discongruence for the term 1-discongruence in the statements of the proven theorems.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号