Алгоритмическая векторная задача

13

У меня есть алгебраическая задача, связанная с векторами в поле GF (2). Пусть v1,v2,,vm - (0,1) -векторы размерности n и m=nO(1) . Найти алгоритм полиномиального времени, который находит (0,1) -вектор u такой же размерности, чтобы u не было суммой любых (logn)O(1) векторов среди v1,v2,,vm . Сложение векторов происходит над полем GF (2), которое имеет два элемента 0 и 1 (0+1=0+1=1 и0+0=1+1=0 ).

Легко видеть существование такого вектора по простому счетному аргументу. Можем ли мы найти u в полиномиальное время? Тривиально найти u в экспоненциальном времени. Я отправлю чек на 200 долларов за первое правильное решение.

Бин фу
источник
он кажется неопределенно связанным с проблемой суммы подмножеств, которая является NP-полной. однако вместо XOR используется полная целочисленная сумма.
vzn
1
странно, я недавно пытался сформулировать и взглянуть на подобную проблему. попробуйте sec13.5 книги stasys jukna о сложности булевых функций. похоже, что ваша q может быть сформулирована в терминах линейных цепей в этой главе.
vzn
1
как насчет супер-поли алгоритмов, т. е. m ^ log (n)?
Димитрис
1
@Niel de Beaudrap: но количество проверяемых XOR супер-поли (то есть примерно (mlog(n)) ), а не поли. Разве это не проблема?
Димитрис
1
Чтобы расширить замечание vzn: казалось бы, что почти любой вектор удовлетворяет вашим требованиям по тому же аргументу подсчета. Я полагаю, что вам также хотелось бы доказать, что (возможно, случайно сгенерированный) вектор не содержится ни в одном подпространстве, охватываемом полилогом ( n ) векторов: так что ваш вопрос равносилен показу того, что проблема определения, является ли кандидат вектор u не принадлежит подпространству, порожденному некоторой размерностью f ( n ) ∈ polylog ( n ) векторов находящихся в NP . vj
Ниль де Бодрап,

Ответы:

8

Там, кажется, опечатка; Я предполагаю, что вы хотите найти который не является суммой ( log n ) O ( 1 ) векторов среди v 1 , , v m (не n ).u{0,1}n(logn)O(1)v1,,vmn

Мне не ясно, работает ли какая-либо константа в для вас. Если вы можете согласиться на суммы менее чем log m векторов, возможно, есть что-то, что нужно сделать. Но если вы хотите, чтобы эта величина была ( log m ) 1 + δ , то я думаю, что это довольно сложно (я давно работаю над этой проблемой).(logn)O(1)logm(logm)1+δ

Тем не менее, вам может быть интересно узнать, что это пример проблемы удаленной точки Алона, Паниграхи и Еханина («Детерминированные алгоритмы аппроксимации для задачи ближайшего кодового слова») для определенных параметров. Пусть и v 1 , , v m будут столбцами матрицы проверки на четность линейного кода в { 0 , 1 } m размерности d = m 1 } n, то есть ( log n ) O ( 1 )m>nv1,,vm{0,1}m (если эта матрица не имела полного ранга, проблема была бы тривиальна). Тогда ваша задача эквивалентна нахождению u { 0 ,d=mnu{0,1}n(logn)O(1) -далее от кода. Эта установка параметров, где размерность очень близка к m, в статье не рассматривается. Тем не менее, они могут только achive удаленности до размерности d = C м для некоторой константы с . На самом деле, я не думаю, что мы знаем о каком-либо сертификате полиномиального размера, который позволяет нам доказать, что некоторый вектор больше чем ω ( log m ) -далее из пространства размерности Ω ( m )logmd=cmcω(logm)Ω(m)не говоря уже о том, чтобы найти его.

Другая связь связана с изучением паритетов в модели ошибок. Если можно эффективно узнать -parities (определенная на 0 , 1 м ) с ошибкой , связанной строго меньше п , то можно установить произвольные значения в первом п - 1 бит U и `` силы ошибка «» в последнем бите, установив его в значение, противоположное прогнозируемому учеником. Это кажется намного сильнее, хотя.(logn)O(1)0,1mnn1u

Проблема также связана с отделением EXP от определенных сокращений до разреженных множеств.

Дэвид
источник
1
Спасибо за указание на опечатку. Последний «v_n» должен быть «v_m». Надеюсь, кто-то это исправит. Ваш ответ содержит полезную информацию. +1
Бин Фу