ГлавнаяАрхивДвоичные решения для больших систем линейных уравнений

Двоичные решения для больших систем линейных уравнений | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/1

Понятие генерической вычислительной сложности распространено на обобщённые регистровые машины над упорядоченным полем. В этом случае машина на каждом входе останавливается и почти на каждом входе даёт содержательный ответ, но может отказаться от вычисления посредством явного уведомления об этом, иными словами, существует особое неопределённое состояние остановки. При этом машина не делает ошибок. Предложен генерический алгоритм полиномиального времени для распознавания систем линейных уравнений без какого-либо двоичного решения, когда число уравнений m близко к числу неизвестных n. Более точно - требуется выполнение двух условий. Во-первых, выполнено неравенство 2n ≥(n-m+1)(n-m+2). Такие системы называются большими, поскольку число уравнений близко к числу неизвестных. Во-вторых, выполнены некоторые предположения общности системы уравнений. Наш подход основан на поиске положительно определённой квадратичной формы среди множества форм, зависящих от параметров. С другой стороны, найден контрпример, показывающий неприменимость этого метода для проверки отсутствия двоичного решения у одного уравнения.
  • Title Двоичные решения для больших систем линейных уравнений
  • Headline Двоичные решения для больших систем линейных уравнений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 52
  • Date:
  • DOI 10.17223/20710410/52/1
Ключевые слова
двоичное решение, линейное уравнение, обобщённая регистровая машина, вычислительная сложность
Авторы
Ссылки
Mucha M., Nederlof J., Pawlewicz J., and Wegrzycki K. Equal-subset-sum faster than the meet-in-the-middle // 27th Ann. Europ. Symp. Algorithms, ESA 2019. Leibniz Intern. Proc. Informatics, LIPIcs. V. 144. Schloss Dagstuhl, Leibniz-Zentrum fur Informatik, 2019. Article 73.
Schroeppel R. and Shamir A. A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems // SIAM J. Computing. 1981. V. 10. No.3. P.456-464.
Bansal N., Gary S., Nederlof J., and Vyas N. Faster space-efficient algorithms for subset sum, k-sum, and related problems // SIAM J. Computing. 2018. V. 47. No. 5. P.1755-1777.
Grigoriev D. Complexity of Positivstellensatz proofs for the knapsack // Comput. Complexity. 2001. V.10. P.139-154.
Mucha M., Wegrzycki K., and Wlodarczyk M. A subquadratic approximation scheme for partition // Proc. Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2019. P. 70-88.
Koiliaris K. and Xu C. Faster pseudopolynomial time algorithms for subset sum // ACM Trans. Comput. Theory. 2019. V. 15. No. 3. Article 40.
Curtis V. V., Sanches C. A. A. An improved balanced algorithm for the subset-sum problem // European J. Operational Res. 2019. V.275. P.460-466.
Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т.М.: Мир, 1991. 702 с.
Селиверстов А. В. О двоичных решениях систем уравнений // Прикладная дискретная математика. 2019. №45. С. 26-32.
Goerdt A. and Lanka A. Recognizing more random unsatisfiable 3-SAT instances efficiently // Electronic Notes in Discrete Math. 2003. V. 16. P. 21-46.
Brown-Cohen J. and Raghavendra P. Extended formulation lower bounds for refuting random CSPs // Proc. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2020. P. 305-324.
Deshpande Y., Montanari A., O’Donnell R., et al. The threshold for SDP-refutation of random regular NAE-3SAT // Proc. Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia: SIAM, 2019. P.2305-2321.
Neumann E. and Pauly A. A topological view on algebraic computation models // J. Complexity. 2018. V.44. P. 1-22.
Blum L., Shub M., and Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines // Bull. American Mathematical Society (N.S.). 1989. V.21. No. 1. P.1-46.
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. IX. Главные универсальные классы и Dis-пределы // Алгебра и логика. 2018. Т. 57. №6. С. 639-661.
Алаев П. Е., Селиванов В. Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // Алгебра и логика. 2019. Т. 58. №6. С. 673-705.
Алаев П. Е. Полиномиально вычислимые структуры с конечным числом порождающих // Алгебра и логика. 2020. Т. 59. №3. С. 385-394.
Коточигов А. М., Сучков А. И. Метод сокращения перебора в алгоритмах построения минимальных аддитивных цепочек // Компьютерные инструменты в образовании. 2020. №1. С. 5-18.
Селиверстов А. В. Симметричные матрицы, элементами которых служат линейные функции // Журн. вычислительной математики и математической физики. 2020. Т. 60. №1. С. 109-115.
Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев // Прикладная дискретная математика. 2019. №44. С. 107-112.
Рыбалов А. Н. О генерической NP-полноте проблемы выполнимости булевых схем // Прикладная дискретная математика. 2020. № 47. С. 101-107.
Рыбалов А. Н. О генерической сложности проблемы представимости натуральных чисел суммой двух квадратов // Прикладная дискретная математика. 2020. №48. С. 93-99.
Рыбалов А. Н. О генерической сложности экзистенциальных теорий // Прикладная дискретная математика. 2020. №49. С. 120-126.
Harris J. and Tu L. W. On symmetric and skew-symmetric determinantal varieties // Topology. 1984. V. 23. No. 1. P.71-84.
Malaschonok G. and Scherbinin A. Triangular decomposition of matrices in a domain // LNCS. 2015. V. 9301. P.292-306.
Schwartz J.T. Fast probabilistic algorithms for verification of polynomial identities // J. ACM. 1980. V. 27. No. 4. P.701-717
Двоичные решения для больших систем линейных уравнений | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/1
Двоичные решения для больших систем линейных уравнений | Прикладная дискретная математика. 2021. № 52. DOI: 10.17223/20710410/52/1