In computational complexity theory, the Orthogonal Vectors (OV) problem is a fundamental problem that is used to prove conditional lower bounds under the assumption that the Strong Exponential Time Hypothesis (SETH) holds. OV is often used as an intermediate problem in fine grained reductions, transferring conditional hardness from SAT under the SETH. The problem takes as input two sets of binary vectors (vectors in which every entry is either 0 or 1) and outputs whether or not there exists at least one pair of orthogonal vectors, one from each set. By the definition of orthogonality, this is equivalent to asking if the dot product of the two vectors is zero.
Problem definition The input to the Orthogonal Vectors problem are two sets of n {\displaystyle n} binary vectors, each of some dimension d {\displaystyle d} :
A , B ⊆ { 0 , 1 } d , | A | = | B | = n {\displaystyle A,B\subseteq \{0,1\}^{d},\quad |A|=|B|=n} . The Orthogonal Vectors problem asks whether there exists at least one pair of orthogonal vectors, one from each set. More formally, OV returns TRUE if and only if there exists some vectors a ∈ A {\displaystyle a\in A} and b ∈ B {\displaystyle b\in B} such that:
a ⋅ b = ∑ i = 1 d a i b i = 0. {\displaystyle a\cdot b=\sum _{i=1}^{d}a_{i}b_{i}=0.}
Example
Consider the following input sets:
A = { ( 1 , 0 , 1 ) , ( 1 , 1 , 0 ) } , B = { ( 0 , 1 , 0 ) , ( 1 , 1 , 1 ) } {\displaystyle A=\{(1,0,1),(1,1,0)\},\quad B=\{(0,1,0),(1,1,1)\}} . For all vectors a ∈ A {\displaystyle a\in A} and b ∈ B {\displaystyle b\in B} , we check if the pair of vectors a {\displaystyle a} and b {\displaystyle b} are orthogonal by evaluating their dot products a ⋅ b {\displaystyle a\cdot b} :
( 1 , 0 , 1 ) ⋅ ( 0 , 1 , 0 ) = 0 {\displaystyle (1,0,1)\cdot (0,1,0)=\mathbf {0} }
( 1 , 0 , 1 ) ⋅ ( 1 , 1 , 1 ) = 2 {\displaystyle (1,0,1)\cdot (1,1,1)=2}
( 1 , 1 , 0 ) ⋅ ( 0 , 1 , 0 ) = 1 {\displaystyle (1,1,0)\cdot (0,1,0)=1}
( 1 , 1 , 0 ) ⋅ ( 1 , 1 , 1 ) = 2 {\displaystyle (1,1,0)\cdot (1,1,1)=2}
There exists one pair of orthogonal vectors, so the solution for these particular input sets is TRUE.
Known algorithms The straightforward algorithm for solving OV checks all pairs of vectors from the two input sets. For each pair ( a , b ) ∈ A × B {\displaystyle (a,b)\in A\times B} , compute the dot product of a ⋅ b {\displaystyle a\cdot b} in O ( d ) {\displaystyle O(d)} time where d {\displaystyle d} is the dimension of the vectors. This algorithm yields a running time of O ( n 2 d ) {\displaystyle O(n^{2}d)} , with the quadradic dependence on n {\displaystyle n} dominating the runtime. However, under certain constraints on the dimension d {\displaystyle d} , faster algorithms are known.
As the dimension d {\displaystyle d} increases, the performance of all of these algorithms excluding the pairwise dot product algorithm deteriorates. This is due to the bit-parallel and combinatorial techniques used by these algorithms become ineffective as the dimensionality of the vectors increases. Particularly, for sufficiently large d {\displaystyle d} , all known algorithms require near quadratic time in the number of vectors. There is no known algorithm running in time O ( n 2 − ϵ ) {\displaystyle O(n^{2-\epsilon })} for any constant ϵ > 0 {\displaystyle \epsilon >0} and for all values of d = c log n {\displaystyle d=c\log n} where c ≥ 1 {\displaystyle c\geq 1} . The existence of such an algorithm would refute the Orthogonal Vectors Conjecture.
The Orthogonal Vectors Conjecture (OVC) The Orthogonal Vectors Conjecture (OVC) formalizes the previously mentioned hardness of the OV problem. OVC states that for vectors of dimension d = c log n {\displaystyle d=c\log n} for any constant c ≥ 1 {\displaystyle c\geq 1} , OV cannot be solved in O ( n 2 − ϵ ) {\displaystyle O(n^{2-\epsilon })} for any constant ϵ > 0. {\displaystyle \epsilon >0.} . The conjecture is widely believed to be true and is closely related to the Strong Exponential Time Hypothesis.
Connection to SETH The connection between Orthogonal vectors and SETH stems from reductions that encode instances of the Boolean satisfiability problem as sets of vectors. At a high level, a Boolean formula can be written as two sets of binary vectors such that a satisfying assignment exists if and only if there exists a pair of orthogonal vectors. The variables of the Boolean formula are partitioned into two groups and partial assignments are encoded to each group as vectors. The coordinates of these vectors represent whether a partial assignment satisfies particular clauses in the formula. Two vectors are orthogonal if and only if the corresponding partial assignments are consistent and satisfy all clauses As a result of this reduction, the Orthogonal Vectors problem is strongly connected to the Strong Exponential Time Hypothesis (SETH). Specifically, if the problem on n {\displaystyle n} vectors can be solved in time O ( n 2 − ϵ ) {\displaystyle O(n^{2-\epsilon })} for some constant ϵ > 0 {\displaystyle \epsilon >0} , then SAT could be solved in time 2 ( 1 − δ ) n {\displaystyle 2^{(1-\delta )n}} for some δ > 0 {\displaystyle \delta >0} , contradicting SETH.
Role in fine-grained complexity The Orthogonal Vectors problem serves as a source of hardness in fine-grained complexity. Instead of reducing a problem directly from SAT, many problems are shown to be hard by reducing from OV, which establishes lower bounds under the assumption that SETH holds. Thus, proving that a problem is at least as hard is OV implies that a faster algorithm for that problem would contradict SETH, making the existence of one impossible if SETH holds.
References