# Distributed K-CSP Solved in O(N²) Successfully Extended to Distributed K-SAT

Oct 31, 2019 · 5 min read

We hope we have achieved the Capability of 1+ Trillion Variables & Clauses with this Breakthrough. Though testing it at scale and verifying the capability will take a whole lot of money and resources, and effort.

# So What is a CSP?

CSP = Constraint Satisfaction Problem

K implies that each constraint can have a ‘maximum’ of K variables.

A constraint satisfaction problem (CSP) consists of

- a set of variables,

- a domain for each variable, and

- a set of constraints.

The aim is to choose a value for each variable so that the resulting possible world satisfies the constraints; we want a model of the constraints.

# What is Distributed K-CSP?

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs.

# There seems to be some confusion in the Definition of Distributed K-CSP. Lets Clarify!

What Distributed K-CSP is NOT!

Lets say you have some variables e.g. 200 variables and some constraints e.g. 1000 constraints.

If we try to solve this problem in its entirety but by distributing the processing across multiple computers. Then it sounds like ‘Distributed’ CSP but this is NOT what is actually meant by Distributed CSP.

This is Distributed K-CSP!

Lets say you have some variables e.g. 200 variables and some constraints e.g. 1000 constraints. And the problem definition itself is distributed across multiple agents running on multiple computers such that each agent has a small set of constraints e.g. 100 constraints which it knows about which nobody else knows about. And it is responsible for choosing/setting the values of a small set of variables e.g. 30 variables.

At no time do all agents have the global knowledge of the problem i.e. all its constraints or all states of all agents in its entirety.

The agents communicate by small asynchronous messages, and do their own parts ‘locally’ i.e. setting their own set of variables as per their best attempts using the knowledge of their own subset of constraints.

This is the ideal description of Distributed K-CSP.

# Some Applications

Distributed Decision Making

Distributed/Remote Agents

Distributed IoT Sensors

Swarm Robotics

Swarm of Drones

Humanoid Army Robots

Border Security

Swarm of Satellites

Distributed Assignment Problems

Distributed Scheduling Problems

Collaborative Planning

# What does this have to do with A.I.?

Constraint Satisfaction Problems were one of the first original approaches to ‘symbolic’ A.I.

Real Intelligence requires Agents to perform in an environment under constraints in coordination with other Agents.

CSP is one of the Grand Problems in A.I.

If you are obsessed with calling Deep Learning as A.I. please see one of the original books on A.I. to understand what A.I. is all about…

# So what is the problem with current Algorithms?

Short Answer: ‘All’ Current Algorithms for solving K-CSP or Distributed K-CSP are exponential in complexity.

The Asynchronous Backtracking has the worst case performance of 2^n where n is the number of boolean variables. It is that basically you will have to set each variable to all possible values and find a solution. And you will do this asynchronously between multiple agents (i.e. Distributed K-CSP)

# What size of problems can we solve today? The limits of Human Technology.

As of today we cannot solve ALL Problem Instances of K-CSP Problems with 200–2000 variables. *sad*

# Equivalent to P vs NP?

Yes! Solving this problem is equivalent to P vs NP. If we can solve Distributed K-CSP in polynomial time or even K-CSP in polynomial time. We prove P=NP.

At Automatski we have proved P=NP in 1990’s. Here are the two last proofs/chapters in the P=NP Proof series.

We have solved more than a dozen NP-Complete Problems in Polynomial Time, including but not limited to K-CSP, K-SAT, Graph Coloring etc.

# So What is the Achievement?

We solved Distributed K-CSP in Polynomial Time O(N²) besides some constant factors.

This is inline with P=NP.

The Algorithm is Complete. It will find ALL solutions or else say No Solutions Exist

The Algorithm is Deterministic

The Agents are Loosely Coupled

The Agents work Asynchronously. w/o any synchronization

The Algorithm is Truly Parallel (compared to Pseudo Parallel Algorithms)

Time to light a cigar…

This is our website http://automatski.com

Written by