Partial Match (Partial Match)

From Algorithm Wiki
Revision as of 12:04, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

Description

In the Partial Match problem, we are given a "database" of $n$ binary strings, and a list of $n$ "queries" which are strings in $\{0,1,?\}^*$. (Here, "?" represents a wildcard.) We say that a query $q=q_1,...,q_d$ matches a string $x=x_1,...,x_d$ if for all $i=1,...,d$, if $q_i$ in $\{0,1\}$ then $q_i = x_i$. Output: Determine for all $n$ queries, which of them match some string in the database.

Parameters

n: number of binary strings/queries

d: length of strings/queries

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem Implication Year Citation Reduction
OV If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$
Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$
2020 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt link

Reductions FROM Problem

Problem Implication Year Citation Reduction
OV If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$
Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$
2020 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt link