Uniform CSP Parameterized by Solution Size is in W[1]. (arXiv:1810.04190v1 [cs.CC])      

Translate

Authors: Ruhollah Majdoddin

We show that the uniform Constraint Satisfaction Problem (CSP) parameterized by the size of the solution is in W[1] (the problem is W[1]-hard and it is easy to place it in W[3]). We study the problem on the Boolean domain, that is {0, 1}. The size of a solution is the number of variables that are mapped to 1. Named by Kolaitis and Vardi (2000), uniform CSP means that the input contains the domain and the list of tuples of each relation in the instance. Uniform CSP is polynomial time equivalent to homomorphism problem and also to evaluation of conjunctive queries on relational databases. It also has applications in artificial intelligence. We do not restrict the problem to any (finite or infinite) family of relations. Uniform CSP restricted to some finite family of Boolean relations (thus with a bound on the arity of relations) can easily be placed in W[1]. Marx (2005) proved that any such problem is either W[1]-complete or fixed parameter tractable. Together with Bulatov (2014) they extended this result to any finite domain. Our proof gives a nondeterministic RAM program with special properties deciding the problem. First defined by Chen et al. (2005), such programs characterize W[1]. Our work builds upon the work of Cesati (2002), which, answering a longstanding open question, shows that parameterized Exact Weighted CNF is in W[1]. This problem is equivalent to uniform CSP restricted to a specific (infinite) family of Boolean relations, where a tuple is in a relation, if and only if the tuple has exactly one 1. Thus, our result generalizes that of Cesati in at least two ways: There is no bound on the size of the tuples of the relations, and the relations do not need to be symmetric.


Share on Facebook Share on Twitter Share on Google+ Share on LinkedIn Pin on Pinterest 

Help prevent us from putting up paywalls send us some coins:
BitCoin BTC 33yzPvrWPcTsmPVdmN1srXv6nNQbWNDgFF
BTC
Etherium ETH 0x9eA967b45c50030AD6b28eB24c7dffE36b902bAA
BTC


Terms Privacy

Cache page has gone blockchain, decryption requests can be posted here: https://etherscan.io/address/0x827F7E8082e678cc3F37C24c0ad012c88DcdfD53#comments
-----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAvxCLc0AVBs69SLe/HJON SeS3avNI2fZKlU6uk8v80uJtIESJ2nB3lFLM7utEyszuHGQvCcb7Qa5Oq+MO+Jdl M3nxbqAcVr8fhBucnU6iQiJACxEFNNFeSVXJbWqY54ik+Qu3oOj+tzQFW4X6wzGa TCYU4cn81a+x+kPYhmzCSOqJfFitES7Y+u1maMc0OKJTCEZgMQXILevpOjXe/0pZ JdtxKS/Chlz7WoIjZZdJd/Lk7CiSwqr9WIBoboAcKGb49RtPmDzBv0Ma1ZscxbiV R8A5NA+FFieoj8VE8KoIXOrQrBA/4zy8iknvLchHMMTqKcd/RbgroPURKJA6Hf95 TQIDAQAB -----END PUBLIC KEY----- -----BEGIN PRIVATE KEY----- MIIEvwIBADANBgkqhkiG9w0BAQEFAASCBKkwggSlAgEAAoIBAQC/EItzQBUGzr1I t78ck41J5Ldq80jZ9kqVTq6Ty/zS4m0gRInacHeUUszu60TKzO4cZC8JxvtBrk6r 4w74l2UzefFuoBxWvx+EG5ydTqJCIkALEQU00V5JVcltapjniKT5C7eg6P63NAVb hfrDMZpMJhThyfzVr7H6Q9iGbMJI6ol8WK0RLtj67WZoxzQ4olMIRmAxBcgt6+k6 Nd7/Slkl23EpL8KGXPtagiNll0l38uTsKJLCqv1YgGhugBwoZvj1G0+YPMG/QxrV mxzFuJVHwDk0D4UWJ6iPxUTwqghc6tCsED/jPLyKSe8tyEcwxOopx39FuCug9REo kDod/3lNAgMBAAECggEBALRNE5uVzIHZFKyLoVCBOWKS8DeAD66ICgft8TbN1+7V 967snr5BRcb1gCiyYf+S9dxa+jyaxr5LlDgGlDko/Tpfh+MiOrvtrfsH53pXGy2X jqIi1KvsK7K+vs9/OX286BmQ4h953+zYrXmZ7HLI21ei1C/iYbLxEt4dqjXoaktN TzWqXuUnCTRjVHKucfTsiZ4KQGM5wkIpaqlVMHHI1s13twUyonzpIgzxukGIPsYd 5QZE3T6dRGkwIcMKR5EgIi2DbYiQIta0pvzGbkpSYc7OGyHvsUU1rCOR1U3P6Jnh ngzhbE3g4XBYO1YnrfiOe+t30RA/dPe7JlFV1OJOl2ECgYEA3wCVV20FGxOqUBCi Lcc7JBK7c8zPJ9ZuFD3Gmw0T8pA31arfPKfn3miy9jNCxd+rg9HsE2tjZoh6kD4q z5mvrmJ+IvqjnzeJuRwBfHXqflHRWrqAdzr1GX0qkgkkzUI041m+3vdT3rTdYxA/ MiRbu1n3SIHfb/SdAG5kLh+7i9UCgYEA21YmdC3wQKs1uM6CutXuFWeEVOznRbw1 STIykQNjx0AOJQ7NEeXX/Il7MzoCwHE2dPmX96M8M5onomvyyZ1iD2j2BIJaqWRQ WKIWMTyTKCNprjrtMwhM6KKs8Q30JeQQ1y2N2I1xrhbRvnxjqnRNpU5OPUN6Zl0r aeRBq4lry5kCgYBLmP4Hojyt3i/JbqocDMM+yl7jtdWwMqAkmoCehYNyonNbKs78 2ArhueqZTe1f+SBC0sJOHwSWeMPb7EdFE1ucKWWLZB5d1k0JBLZ4Q90Xr5LiSAFO 6hy25FivIwxnzP7y57SuD3hOMlAuyg4yaGL0k14iJWzinjEvOT0a6cUBdQKBgQCr uOFWaHkHSIRA8n3rpX5Hh8pVaz0OnfHiIsjwPAUshHwOi24GqzrU3xZz3uE0pe6K 2rceDNEfXXvWcEmfi/awNe8XTK+Km51EJ3LUjaZw8HjXDg+TutXr9SENgW07FToS HfpGJ0dvkzIXvu+RDomT+KDM2j3EUwGgYDMCCA87UQKBgQDbQt/70ZTsPyv+26zz Fhyw3H4Tr4JJSskb54C/QJtvb7uf6n4YfBF4yfZ0u76m4shzabt/kVcW7Y5DJ7TM hRdJREiyNBNCLH0iiQU5TNtio5hu9E3YrZ3shPs+CGwzOkLXUTpBgEXhbiZBaJl+ SbX4dyW8++unArtI+2aG6zo/8Q== -----END PRIVATE KEY-----