## Creating a list that shows the numerical values not in boolean form

Based from the equation I used in the code below, I found how many values are divisible by 5. However, this is in boolean form. I only know how many are divisible by 5. I need to formulate a conjecture by exploring the values, but I’m having trouble figuring out how to create a list that gives me the numerical values that are divisible by 5 based from given function. Here’s is my program.

expn = Flatten[Table[1^n + 2^n + 3^n + 4^n, {n, 1, 10000}]]; sumpowern = Mod[Total /@ expn, 5] ; Count[sumpowern, 0] posints = Length[Select[Divisible[Total /@ expn , 5], TrueQ]]  

## Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

For example, for a boolean matrix of size $$3×4$$, the row sum vector $$R = (3, 3, 0, 0)$$ and the column sum vector $$C = (2, 2, 2)$$ form a match because I can construct the boolean matrix:

$$\begin{matrix} & \begin{bmatrix} 1 & 1 & 0 & 0\ 1 & 1 & 0 & 0\ 1 & 1 & 0 & 0 \end{bmatrix} & \begin{pmatrix} 2\2\2 \end{pmatrix} = C \ R = &\begin{pmatrix} 2 & 2 & 0 & 0 \end{pmatrix} \end{matrix}$$

However, the column vector $$C’ = (4, 1, 1)$$ doesn’t form a match with $$R$$.

So given two vectors whose values are sorted in descending order $$R_{1, w}$$ and $$C_{h, 1}$$, and whose accumulated sum is the same, $$T = \sum_jR[1, j] = \sum_iC[i, 1]$$, how can I polynomically check if $$R$$ and $$C$$ form a matching because I can form a matrix $$M_{h,w}$$ having $$R$$ and $$C$$ as row and column sum vectors?

More specifically, in case it can help to make the check algorithm faster, in my specific case, R and C has the following properties:

• $$h \leq w$$
• The number of positive values of $$R$$ and $$C$$ is $$> w$$. For example, $$R$$, in the example, has two positive values and $$C$$ has three positive values, and it happens that $$2 + 3 > w = 4$$.
Posted on Categories proxies

## Unsigned/signed boolean Answer is c). I understand that the expression evaluates to true but what does signed/unsigned have to do with booleans?

Posted on Categories proxies

## Computational complexity in Boolean network

An Boolean control networks can be expressed as $$\begin{equation} \label{ControlBN} \left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ {x_{2}(t+1)=f_{2}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ {\vdots} \ {x_{n}(t+1)=f_{n}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ \end{array}\right. \end{equation}$$ where $$x_i,~i=1,\dots,n,$$ are state nodes, $$x_i(t)\in\{0,1\},\,i=1,\cdots,n$$ are the value of the state node $$x_i$$ at time t. $$u_i,~i=1,\dots,m$$ are control nodes, $$u_i(t)\in\{0,1\},\,i=1,\cdots,m,$$ are the value of the state node $$u_i$$ at time t, and $$f_i:\{0,1\}^{n+m}\rightarrow \{0,1\},\,i=1,\dots,n$$ are Boolean functions.

Consider the above system, Denote its state space as $$\mathcal{X}=\{(x_1,\cdots,x_n)|x_i\in\{0,1\},i=1,\cdots,n\}.$$

Given initial state $$x ( 0 ) = x^0\in \mathcal{X}$$ and destination state $$x^d\in \mathcal{X}$$. Destination state $$x^d$$ is said to be reachable from the initial state $$x^0$$ at time $$s>0,$$ if there exists a sequence of controls $$\{u(t)|t=0,1,\cdots,s-1\}$$, where $$u(t)=(u_1(t),\cdots,u_m(t))$$, such that the trajectory of the above system with initial value $$x^0$$ will reach $$x^d$$ at time $$t=s.$$

The above system is said to be controllable, for any $$x^0,x^d\in \mathcal{X},$$ $$x^d$$ is reachable from $$x^0.$$

$$M$$-step Controllability Problem is defined as

Input: Given an Boolean Control Networks with $$n$$ state variables $$x_1,\cdots,x_n,$$ $$m$$ controls $$u_1,\cdots,u_m,$$ Boolean function $$f_1,\cdots,f_n:\{0,1\}^{n+m}\rightarrow \{0,1\}.$$ Given constant $$M.$$

Problem: for any destination state $$x^d$$ and initial state $$x^0$$, whether or not there exists a sequence of controls $$\{u(0),\cdots,u(M-1)\}$$ such that $$x^d$$ is reachable from $$x^0$$?

In order to solve this problem, I convert the problem into logical form as following:

$$\begin{equation*} \begin{split} &\forall x_1(0)\cdots\forall x_n(0)\forall x_1(M)\cdots\forall x_n(M)\exists u_1(0)\cdots\exists u_m(0)\exists x_1(1)\cdots\exists x_n(1)\cdots \exists x_1(M-1)\cdots\exists x_n(M-1)\ &\exists u_1(M-1)\cdots\exists u_n(M-1)~~\bigwedge_{i=1}^{n}(f_i(x(0),u(0))\leftrightarrow x_i(1))\wedge \bigwedge_{i=1}^{n}(f_i(x(1),u(1))\leftrightarrow x_i(2))\wedge \cdots\wedge \ &\bigwedge_{i=1}^{n}(f_i(x(M-1),u(M-1))\leftrightarrow x_i(M)).\ \end{split} \end{equation*}$$

According to such expression, I can prove the upper bound of the problem. But I have no idea about how to prove it is $$\Pi_2^p$$-hard.

Posted on Categories proxies

## Finding a boolean submatrix isomorphic to a specific set of other boolean matrices

Given a matrix $$M$$ of certain size $$h\times w$$, where $$h\leq w$$, for example $$5\times 6$$, are also given the following set $$A$$ of (a)dditional matrices:

$$\begin{matrix} Matrices: & \begin{bmatrix} % 2 x 5 1 & 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 3 x 4 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 4 x 3 1 & 1 & 1\ 1 & 1 & 1\ 1 & 1 & 1\ 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 5 x 2 1 & 1\ 1 & 1\ 1 & 1\ 1 & 1\ 1 & 1 \end{bmatrix}\ Sizes: & 2 \times w – 1 & 3 \times w – 2 & 4\times w – 3 & 5\times w – 4 \end{matrix}$$

As you can see, this specific set of matrices follows the pattern of containing only $$1$$s, with sizes starting from $$2\times w – 1$$ up to $$h\times w – h + 1$$.

The problem is finding a submatrix of $$M$$ that is isomorphic with any of the matrices in the set $$A$$. In case there is more than one solution, the result is any submatrix of maximum height first, and in case there’s again multiple candidates, any submatrix with maximum width.

The problem have the following properties:

• $$2 \leq h \leq w$$.
• Each row of $$M$$ has at least one $$0$$.
• Deduced from the way $$A$$ is generated, for each $$a\in A$$ of size $$a_h\times a_w$$, it happens that $$a_h + a_w – 1 = w$$.
• The operations you can apply to $$M$$ to check for homomorphism are the usual ones, you can swap rows between them, or columns betweem them, but you cannot sum or substract rows or columns between them as in lineal algebra.

I have spend already a couple of days trying to construct a polynomial-time algorithm for this problem but I don’t see it clearly. Is this problem NP-hard, taking into account all of the restrictions it has?

I’m looking for any strategy that implies to "normalize" $$M$$ by applying a set of row or column swapping in a way that, in case there’s a solution, it’s in the "top left" corner of $$M$$. I have also explore the possibility of using the rank of $$M$$ to see if there’s some pattern regarding its potential solution, etc. I have also try to sort the columns and rows by number of $$1$$s and that kind of things, but my background on lineal algebra in very limited, and so it is my set of mathematical "tricks" to characterize $$M$$ regarding $$A$$.

NOTE: The maximum subarray problem is similar to this one, but take notice that my best solution is not neccesarily the maximum one. If, for example, the solution submatrices of size $$3\times 4$$ and $$5\times 2$$ exists, the "best solution" is $$5\times 2$$, because it has a bigger height, although it’s has less number of $$1$$s.

NOTE: The graph homomorphism problem is also similar, but take notice that $$M$$ is not equivalent to an adjacency matrix because it’s not square or symmetrical.

Posted on Categories proxies

## Integrating multidimensional PDFs on Boolean cube separated by hyperplane

Problem Statement: Let $$f:[0,1]^d \rightarrow [0,1]$$ be a $$d$$-dimensional probability density function. Further, for $$c\in [0, 1]$$ and $$\mathbf{w}\in \mathbb{R}^d$$, let $$H = \{\mathbf{x} \in [0,1]^d : \mathbf{w}\bullet\mathbf{x} = c\}$$ be a hyperplane. This separating hyperplane partitions partitions the unit hypercube $$[0, 1]^d$$, into two regions,

$$U = \{\mathbf{x} \in [0,1]^d :\mathbf{w} \bullet \mathbf{x} > c\} \quad \text{ and }\quad L = \{ \mathbf{x} \in [0, 1]^d: \mathbf{w} \bullet \mathbf{x} \leq c\}$$

Under what conditions on $$f$$ can one efficiently compute (approximately or exactly) the cumulative probability of $$f$$ over $$L$$ (or equivalently over $$U$$), i.e. $$\int_{L} f(\mathbf{x})d\mathbf{x}$$?

Preliminary Ideas: If $$f$$ is something like the uniform distribution then the integral can be computed exactly. For sake of example, suppose that $$\mathbf{0}\in L$$ and $$H$$ represents the upper limits of integration. Then we are integrating

$$\int_{0}^c\int_{0}^{\frac{c – w_dx_d}{w_{d-1}}}\dots\int_{0}^{\frac{c – w_2x_2 – \dots w_dx_d}{w_1}} 1 dx_1 \dots dx_{d-1} dx_d$$

Which each integral has a closed form solution derivable in polynomial time, and there are only $$d$$ number of integrals. Assuming this is correct, then if $$f$$ is any polynomial it can also be solved exactly.

Question Are there any characteristics, or common families of PDFs in which this problem is polynomial time solvable? In practice, PDFs such as a Gaussian are computed numerically, is there any literature on how well of a numerical approximation can be achieved in this setting, for $$d$$-dimensional PDFs which are computed numerically?

Posted on Categories proxies

## Boolean Lattice Implementation

Let $$X = \{1,2,\dots n\}$$, and $$Y= \{ S\subset X: |S|\le 2\}$$. I am interested in "avoidance sets" $$A \subset Y$$ which logically are supposed to correspond to $$f(A):=\bigwedge_{a\in A} \lnot a$$ in the Boolean lattice defined over $$\mathcal{P}(X)$$. (if $$A = \{\}$$ it shall correspond to $$X$$, the maximal element of our lattice)

Given a list of avoidance sets $$A_1,A_2,\dots A_k$$, I want to return an avoidance set $$A’$$ such that $$f(A’)$$ is the least upper bound of $$\bigvee_{1\le i \le k} f(A_i)$$. (by least upper bound I mean the least upper bound which can be represented by an avoidance set)

Can this be done in time linear to $$\sum_{1\le i \le k} |A_i|$$? (you may assume that all the sets $$A_i$$ are simplified, i.e. if $$\{a\}\in A_i$$ and $$\{b\}\in A_i$$ then $$\{a,b\} \not \in A_i$$)

Posted on Categories proxies

## Making complex boolean circuits that give true as output only for a specific combination of boolean inputs

This is my first question on a stack exchange website so please bear with me. I am making challenges for a jeopardy style capture the flag event in my college and I had come across the minetest challenge in the hardware section of google CTF qualifier conducted last year. A clean and organized solution to this problem has been provided by liveoverflow.

I would like to design a simpler version of this problem for my college’s CTF event but I am unable to design a complex circuit that gives true output only for a specific combination of inputs. I know that a circuit with this functionality is not very difficult to implement and just needs to represent the following logic:

trueinput1 AND trueinput2 AND ... NOT falseinput1 AND NOT falseinput2 ...  

However I want it to be vast and complicated so that participants cannot decode its functionality just by doing a visual analysis. Is there any technique to complicate the boolean logic above and to design a corresponding circuit that looks ugly even for a small number of inputs(32/64).

Posted on Categories proxies

## Partially defined boolean function

Consider boolean function $$f(x_{1}, x_{2}, \dots, x_{n})$$. The value of $$f$$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $$?$$). It is possible to set $$f$$‘s value on some inputs, no matter if they were initially defined.

The problem is to set some of the inputs such that:

• all initially undefined inputs become defined (i. e. no $$?$$ in function truth table);
• $$f$$ is monotone in the common sense.

The optimization part is to use the minimum possible assignments. How can one find an optimal way in the time $$\mathcal{O} \left( p(n) \left( 2^{n} \right)^{2} \right)$$, where $$p(n)$$ is polynomial?

Posted on Categories proxies

## Boolean circuit multigraph

Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer]. He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some functions which come from a set of possible operations (called basis).

Let us say that we only allow the operation $$\land$$ for our circuit (i.e. the basis only consists of $$\land$$). Is $$x \land x$$ a circuit if $$x$$ denotes an input gate? I don’t think so, because the input gate $$x$$ is only allowed to occure once in the graph and then we would need two edges to the $$\land$$-node, i.e. we would need a multigraph. A way around would be to force a basis to have an identity operation. For instance using the basis $$\land, id$$ we could of course build the $$x \land x$$ circuit (this is also the case if we can build the identity operation in any other way, e.g. if we have $$\neg$$ in our basis) even though we have to increase the size of the circuit by using $$id$$. It seems very counterintuitive that such a simple circuit is in fact not a circuit over the basis $$\land$$, so is my reasoning correct?

[Vollmer] Heribert Vollmer, Introduction to Circuit Complexity