# Question
Title: Exactly why the time taken by 'memory reads', is not considered while calculating time complexity of an algorithm?
I am sorry if I sound repetitive(I've asked a similar sounding question earlier - Relevance of memory reads while calculating the time complexity of an algorithm). Actually, it didn't answered my intended query. May be I framed the question inappropriately, and in an unnecessarily complex and indirect way.

In the current/present question, I am referring to the magnetic disk memory as it definitely takes much time, but if the primary memory(RAM) also does take much time relative to processing, then it can too serve the purpose here.

Also, I am specially concerned here with the algorithms where number of memory reads are some function of 'n', instead of being nearly constant(because in latter case, this question is not applicable or doesn't make sense anyway).

# Answer
> 4 votes
People don't usually refer to the hard drive as "memory" though the term "external memory" is common in this area of the literature. As far as disk accesses are concerned, they *are* taken into account in the analysis of algorithms that are explicitly written to access disk. Some of the more popular models are the two-level external memory model, the parallel disk model, and the cache-oblivious model. There are also hierarchical memory models. Algorithms and Data Structures for External Memory particularly chapter 2 describes the parallel disk model in detail, briefly describes other external memory models, and provides pointers into the literature. Some of these ideas and results go back about half a century.

---
Tags: algorithms, algorithm-analysis, asymptotics, memory-access
---


title: Algorithm for 3-object matching

text:
# Question
Title: Algorithm for 3-object matching
I believe that in the general case stable matching for 3 members rather than 2 is NP-Complete, but I wonder if in my case there's something that I am missing that could have reasonable time complexity.

The specific purpose of the program I am trying to write is to take an arbitrary number of objects and split them into groups of 3. Hypothetically, each object has a color (let's say right now there's 10 possible colors).

The part of this group creation that allows something of a "preference list" of other members is both having group members of different colors and having been grouped with them in the past as little times as possible.

Everything I have come up with either has horrendous time complexity or has the chance of failing (missing possible groupings). If anyone has done anything like this before I would appreciate any suggestions.

# Answer
It sounds like you're looking for a polynomial-time approximation algorithm for the 3-dimensional matching problem (which is, as you noted, NP-complete - the decision problem is one of Karp's 21 NP-complete problems).

In 2014, Ostrovsky and Rosenbaum proved that 3D matching is APX-complete. This implies the existence of an efficient algorithm that produces a result within a "fixed multiplicative factor of the optimal answer" - in their case, $4/9$.
> 1 votes

---
Tags: algorithms, graphs, time-complexity
---


title: HMM tagger - Baum Welch training

text:
# Question
Title: HMM tagger - Baum Welch training
I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, that would leave us with $459^2$ states and $(459^2)^2$ transitions between them, which would require a massive amount of memory.

Are there any workarounds around this? What I thought of is considering only bigrams seen in the data, but it is still a lot of memory.

# Answer
Actually, there are only $459^3$ transitions, not $459^4$ transitions. That helps a lot. This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$. In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags). So, there are at most $459^3$ transitions, or at most about 100 million transitions. You should be able to store that a graph with 100 million edges in memory without too much difficulty.

My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.
> 1 votes

---
Tags: natural-language-processing, statistics, hidden-markov-models
---


# Question
Title: Min spanning tree that preserves total weight of original graph
I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i.e. have the smallest number of edges while maintaining fairness.

I've noticed that you can eliminate edges when you owe person A who owes person B, but you also owe person B. Therefore, you can take on the debt of A directly, reducing the size of the graph to two edges instead of 3:

```
   ME                   ME
  /  \                 /  \
 /    \               /    \
B <--- A     ====>   B      A

```

*(ME points to A and B)*

I'm having trouble coming up with a general approach for this, and I'm not sure what to google since this is an unusual use of spanning tree.

I've thought about building up the graph one edge at a time, then analyzing what simplifications can be made, but the build order seems to matter and often does not produce the most optimal graph.

**Edit: formalized constraints**

There is a set of individuals $p$ that may owe each other money. For any pair $(p\_i, p\_j)$, if they owe each other money, it is one directional, i.e. $p\_i$ cannot owe money to $p\_j$ if $p\_j$ owes money to $p\_i$.

You are given a list with entries $p\_x \to p\_y, n$ where $n \in R$. This means that $p\_x$ owes $p\_y$ $n$ amount of dollars.

Your goal is to return a list of identical form with the following constraints:

* It is fair in the sense that each individual in $p$ incurs a wealth difference as if the transactions in the original list were performed.
* It is the shortest such list possible

# Answer
Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta\_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum\_{i=1}^n \delta\_i = 0$. After all transactions have cleared, the capital of person $i$ should change by $\delta\_i$. I will now show how to implement this scheme using at most $n-1$ transactions, using an iterative procedure.

If all $\delta\_i$ are zero then no transactions need to be done, so we can assume that there exists some non-zero $\delta\_i$. Let $i$ be a person such that $|\delta\_i|$ is minimal. Since the $\delta\_i$ sum to zero, there must be some $\delta\_j$ with opposite sign. By our choice of $\delta\_i$, $|\delta\_j| \geq |\delta\_i|$. If $\delta\_i \> 0$ then we tell person $j$ to pay person $i$ the amount of $\delta\_i$, and if $\delta\_i \< 0$ then we make the opposite transaction. We update the $\delta$ vector accordingly: $\delta\_i := 0$ and $\delta\_j := \delta\_j + \delta\_i$ (maintaining the invariant that the $\delta\_i$ sum to zero), and continue to the next iteration. In each iteration we zero out at least one $\delta\_i$, so in iteration $n-1$ there will be at most two non-zero $\delta\_i$, which will both be zeroed during the iteration (since they sum to zero). This shows that there are at most $n-1$ transactions in total.

---

Minimizing the total number of transactions is NP-hard, by reduction from the following problem:

> Given $n$ numbers in the range $\[-n,+n\]$ summing to zero and an integer $k$, can the numbers be partitioned into $k$ sets summing to zero?

This problem is shown to be NP-hard on math.se.

We will reduce this problem to the following:

> Given an owe graph and an integer $\ell$, can the graph be implemented using at most $\ell$ transactions?

Suppose that we are given a list of $n$ numbers $x\_1,\ldots,x\_n$ summing to zero and an integer $k$. Running the algorithm above, we construct an owe graph in which $\delta\_i = x\_i$. I claim that this owe graph can be implemented using $n-k$ transactions iff the list can be partitioned into $k$ parts summing to zero.

Suppose first that the list can be partitioned into $k$ parts summing to zero. Running the algorithm above for each of the parts, we end up with $n-k$ transactions. Conversely, suppose that the graph can be implemented using $n-k$ transactions. Thought of as a graph, these support at least $k$ connected components, each of which corresponding to a list summing to zero.
> 4 votes

---
Tags: graphs, shortest-path, spanning-trees
---


# Question
Title: A Turing machine going to the right by the first $2 |w|$ steps
A single-tape Turing machine $M$ has the property that, for every input $w$, during the first $2 |w|$ steps, the head of $M$ moves only right (it does not move left nor stays in place); the machine is also allowed to halt at any moment during these first $2|w|$ steps. Prove that the language of $M$ is in $DTIME(n)$.

Perhaps I don't understand the problem because I don't know how to start. My intuition is following:

$L$ reconized by $M$ is $= K \cup M$ where $K$ is a set of such words $s$ that $|s| \< |w|$. $M \cap K = \emptyset$.

We can consider two situation:

1) $M$ stops before $2|w|$ steps. It means that such word $w$ can be represented by regular expression. Therefore, such words can be accepted/rejected in $DTIME$.

2) $M$ stpes $2|w|$ to the right (or more) and now it can come back to the beginning. But, if machine is able to reach $2|w|$ steps without memory it means that $M$ can compute steps in any way. It cannot be "solved" using a tape- the machine cannot move left so the tape is useless. So, the information must be encoded in states. But, number of states is finite. So, let $|Q| = n$.

Then, there is limited number of such words that cannot be recognized using a deterministic automata. The limited language can be recognized in $DTIME$. Other words can be recognized by deterministic automata.

It is my idea. I am not sure if is ok.

1) Is it?

2) Probably there is a better (one-sentence) solution. Please say me.

# Answer
Suppose that the Turing machine has $N$ states. We call a state $q$ *reachable* if for some word $w$ of size at least $N$, when the Turing machine runs on $w$, it finds itself in state $q$ after reading $w$. During the following $N$ steps, the machine must go to the right. If it doesn't halt during these $N$ steps, then some state is repeated, and so the machine never halts. Since we assume that it does always halt, it follows that when the Turing machine is in state $q$ with an empty symbol under the head, it stops within $N$ steps, during which it continues traveling to the right.

The discussion above shows that if $w$ has size at least $N$, then the Turing machine halts within $|w|+N$ steps. This shows that the machine runs in linear time $O(|w|)$, which implies your exercise.

With a bit more work, you can show that the language accepted by the machine is in fact regular. Indeed, if we only consider words of length at least $N$, then we have a machine moving only to the right, so we know that $L(M) \cap \Sigma^N \Sigma^\*$ is regular. Since $L(M)$ differs from this language by finitely many words, it follows that $L(M)$ is regular.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?
I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here:

```
int cash(int x, int y){
    int h = seed + x*374761393 + y*668265263; //all constants are prime
    h = (h^(h >> 13))*1274126177;
    return h^(h >> 16);
}

```

However, for the thing I'm working on, I have the added restriction of only using arithmetic operations. the operations I have available are: `+`, `*`, `-`, `/`, `%`, `sign()`, `abs()`, `pow(base, exponent)`, `ln()`, `floor()`, as well as basic trig functions. I'm having difficulty finding anything that doesn't rely on having bitwise operations available. Does anyone know of a hash function that doesn't use xor, that produces reasonable visual randomness when fed a linear sequence of integers?

# Answer
> 3 votes
Found a solution here, as glsl, which at one time had near exactly the same restrictions I wanted:

```
float rand(vec2 co){
    return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

```

or as I implemented it: $\operatorname{mod}\left(\sin \left(a\cdot 12.9898+b\cdot 78.233\right)\cdot 43758.5453,\ 1\right)$

# Answer
> 2 votes
Low-discrepancy sequences might do what you want. Depending on what you want, they might be more useful than pseudo-random sequences. If you need more than one dimension, Halton sequences are popular.

This probably isn't going to help you in a code golf scenario, though.

---
Tags: hash, graphics, pseudo-random-generators
---


# Question
Title: Can proofs-of-work be probabilistically checkable?
I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site.

## **Question**

Because of the nature of a blockchain, a large number of publicly agreeable coin flips may be generated - namely, the hashes of previous blocks may be agreed by the network to be randomly drawn from $\\{0,1\\}$.

Accordingly, has anyone attempted to create a solution to the Byzantine Generals' Problem for a blockchain, where a proof-of-work is a decision problem in $NEXP$ or $PSPACE$, and the proof is *checked probabilistically*, using hashes of previous blocks as public coin flips?

## **Motivation**

I’ve seen discussions online attempting to make a proof-of-work for cryptocurrencies "better," by, for example, finding witnesses to $NP$ problems.

A prover who finds a witness to an $NP$ problem may publicly announce the witness to prove that she did the work.

If there were a common, static pool of $NP$ problems, say $TSPs$ of subsets of the $n$ largest cities on Earth, then *announcing the witness* to secure block $i$ means that anyone can take that same witness and attach the work to another chain, which does not secure the chain.

If the verification were a zero-knowledge proof, the world (apart from the prover) may never need to know what the witness actually was.

However, as noted by others, because cryptocurrencies are trustless peer-to-peer systems, attempting to keep such a witness zero-knowledge may be difficult in a trustless peer-to-peer system.

For example, if a prover finds a solution to one of the $TSP$ problems from a static pool, and announces a $ZKP$ proof, she may still be tempted to sell her witness to fraudster if the price was right. That fraudster may attach the work to another fraudulent chain.

The witness to an $NP$ problem may not secure a blockchain, which is one of the purposes of a proof-of-work.

## **Similar Proposals**

Converting the problem space from a static pool of $NP$ problems to a dynamic pool of problems may help, and I’ve seen a proposal that, I think, dynamically generates subgraph isomorphism problems as proofs-of-work. However, as far as I can tell, the above proposal verifies the witness deterministically.

I’ve also seen attempts to use PCP’s to verify outsourced computations, although I don’t think the outsourced work is connected to a cryptocurrency blockchain. Maybe that work comes close.

## **History**

In **\[GMR85\]**, the authors introduce interactive proof systems. In **\[GS86\]**, the authors show a public coin protocol for graph nonisomorphism. In **\[Sha91\]**, the author proves $IP=PSPACE$.

In **\[BFL91\]**, the authors prove that $MIP=NEXP$. In **\[BFLS91\]**, the authors envisioned extending those ideas to transforming formal mathematical proofs into *transparent proofs* checkable in polylogarithmic time.

In **\[AS92\]**, the authors characterized the above works as implying that mathematical statements can be checked in polylogarithmic time by reading only $poly(logn)$ bits in a proof of a theorem of Peano arithmetic, with a proof of size $n$ (which they reduced to a sublogarithmic number of bits, and was reduced contemporaneously to $O(1)$ queries in the hallowed PCP theorem).

E.G., quoting from **\[AS92\]**, they envision statements:

$$\\{(T,1^n):T\\:is\\:a\\:theorem\\:of\\:Peano\\:arithmetic\\:with\\:a\\:proof\\:of\\:size\\:\leq n\\}$$

as languages in $NP$, with witnesses that can be probabilistically checked with a sublogarthmic number of bits.

Note that it is undecidable to find an easy relation between $|T|$, the length of the theorem proved, with $|\pi|=n$, the size of the proof. Simple provable statements may have long proofs, or long provable statements may have short proofs.

That is, by the Incompleteness Theorem, $n$ grows faster than any computable function of $|T|$. Accordingly, one may consider a bounded version of the above, say $n=O(exp |T|)$, and find exponential size proofs of small theorems. Thus, statements such as:

$$\\{(T,1^n):T\\:is\\:a\\:theorem\\:of\\:Peano\\:arithmetic\\:with\\:a\\:proof\\:of\\:size\\:O(exp(|T|))\\}$$

may be viewed as languages in $NEXP$, with inputs of size $|T|$.

**\[AS92\]** states “we suspect this result is largely of *theoretical (as opposed to practical)* interest” (emphasis added.)

In **\[Kil92\]** the author describes a prover committing to a probabilistically checkable proof of $\pi$ as a Merkle root of a tree, and answering public questions about bit $i$ of the proof by revealing the path of $i$ to the publicly committed Merkle root.

In **\[Nak08\]** the author’s solution of the Byzantine Generals' Problem entails requiring proofs-of-work.

The proof-of-work in **\[Nak08\]** involves partially inverting cryptographic hashes – for example, given a cryptographic hash $h(x)\in\\{0,1\\}^N,x\in\\{0,1\\}^\*$, a block $i\in\mathbb{N}$, and (a Merkle root of) financial transactions $B\_i\in\\{0,1\\}^N$, finding a nonce $n$ such that $$h(n\Vert B\_i)$$ begins with a number $d$ of leading $0s$.

The proof-of-work in **\[Nak08\]** has some advantages – it secures the transactions, relying on the well-established SHA256 hash ($N=256$), etc. The difficulty of finding a nonce grows as $O(2^{kd})$ for some $k$. The proof-of-work in **\[Nak08\]** is *immediately checkable* by all nodes in time $O(d)$, and verification is very fast.

Likewise, there may be disadvantages to partially inverting SHA256 – a lot of energy is spent on a problem that is essentially a random, somewhat artificial puzzle. Additionally, *all* those who attempt the proof-of-work are working on *the same problem*, while there will on be *one* "winner."

## **Examples**

**NEXP**

Consider, for block $i$, a prover committing to a Merkle-root, as in **\[Kil92\]**, of a proof $\pi$ of some statement $T$ of Peano arithmetic in probabilistically checkable format, as in **\[AS92\]**. She may use in the proof the Peano axioms and other rules of inference. She may also use other theorems proved in previous blocks as lemmas to speed up the proof of her own theorem. The first miner to announce proofs of statements where $\sum2^{-|T|}\>d$ for some difficulty threshold $d$ "wins" the block.

She then uses the hash of block $i-1$ as the random coin tosses used by the verifier in **\[Kil92\]** to query $O(1)$ bits of $\pi$.

As her reward for mining, she is granted a profit of $\sum2^{-|T|}$ units of currency. Hence she is encouraged to find proofs of small theorems (as they are worth more).

This also keeps the total amount of minted currency finite, and bounded below by I think $1/2$ (because $1/2$ of all well-formed formulae are true and $1/2$ are false, and not all of them can be proved.)

I also think this encourages $|T|$ to grow only as $O(log\\:i)$, where $i$ is the block number, because miners only look at smaller statements.

This also shows that a miner who proves a statement $T$ can also announce $\sim\sim T$, and $\sim\sim\sim\sim T$, etc., and still only be rewarded $2^{-O(|T|)}$ units of currency.

Eventually the world may learn that some small statement of Peano arithmetic is true, although no one person or miner may have access to the entire proof. Some miners may have proved individual lemmas, which are used by others to finish off the proof. Those other miners may never need to have their proofs verified deterministically.

**PSPACE**

As another example for a proof-of-work, consider adding a number of randomly spawned quantified Boolean formula ($QBF$) to a “pool” of open problems. Say, upon mining block $i$, $O(1)$ $QBF$ problems with an average of $l=O(log\\:i)$ literals are spawned and added to the “pool.”

The problems added to the pool may be randomly generated based on the previous blocks’ hash.

Provers (miners) compete to find proofs that one or more of the problems in the “pool” are true or false. The first prover to find a number $d$ of statements in the "pool" wins the mining profit. Upon finding a proof, a prover engages in a public-coin interactive proof of the truth or falsity of the statements that they proved. I think they can engage in the Fiat-Shamir heuristic in their announced proof.

Provers are not, necessarily, required to prove that the most recently spawned problems are true or false, only that *some* of the problems in the pool are true or false. For example, a problem added $10$ or $100$ blocks ago may still be worked on and proved for this block.

Hence a problem that has been “in the pool” for a long time will manifest itself as a harder problem because it’s been “in the pool” for longer.

The provers may be rewarded $2^{-l}$ units of currency. Hence there is an encouragement to find true QBF's with a smaller number of literals. This also keeps the total currency finite. Because some QBF's with a large number of literals may be easier than others with a small number of literals, it might be easier for miners to work on newly added, easier problems with a larger number of literals than older, harder problems with a fewer number of literals, although the profit may be lower.

Unlike inverting SHA, provers $P\_1$ and $P\_2$ do not need to be working on the same position at the same time. Whoever finds a proof first merely announces her proof, relying on the random bits from the hash of the previous block to verify probabilistically. The loser for this block *may still continue searching* for her proof, and may win the next round.

Because $PSPACE$ can be considered as games between $\exists$ and $\forall$, mining may be considered as solving games. Eventually the world may find out that chess (or whatever game) is solved. However, no one prover has access to the entire proof, because no one prover will be able to store the entire proof.

## **References**

**\[AS92\]** S. Arora, S. Safra. Probabilistic Checking of Proofs: A new characterization of NP. link

**\[BFL91\]** L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive proofs. link

**\[BFLS91\]** L. Babai, L. Fornow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. link

**\[GMR85\]** S. Goldwasser, S. Micali, C. Rackoff. The Knowledge complexity of interactive proofs. link

**\[GS86\]** S. Goldwasser, M. Sipser. Private coins vs. public coins in interactive proof systems. link

**\[Kil92\]** J. Killian. A note on efficient zero-knowledge proofs and arguments. link

**\[Nak08\]** S. Nakomoto. Bitcoin: a Peer-to-Peer Electronic Cash System. link

**\[Sha92\]** IP=PSPACE link

# Answer
I believe the answer to the question is, for all intents and purposes, "yes, this idea is being explored in **\[BRSV17\]** (link)."

For example, given two sets $S$ and $T$ of $d$-dimensional vectors with $|S|=|T|=n$, the $2$ Orthogonal Vectors $\text{(2OV)}$ problem is to find a vector $\sigma\in S$ and $\tau\in T$ such that $\langle\sigma,\tau\rangle=0$. This can be extended to a $\text{kOV}$ problem.

In **\[BRSV17\]**, the authors show how to convert the $\text{2-OV}$ problem into an Merlin-Arthur protocol that can be extended to a *Proof of Useful Work*, and extend the problem to a $k$-round Interactive Proof.

The authors do this by converting the problem into a Sum Check protocol to determine the value of a polynomial $\text{GOV}$ over a field $\mathbb{F}$ at a random point $x\in\mathbb{F}$. The Sum Check protocol is a predecessor of the **\[Sha92\]**, **\[BFL91\]** and **\[BFLS91\]** protocols.

The authors further disclose a blockchain including the Proof of Useful Work, wherein posers add $\text{kOV}$ problems to a common pool, and miners follow the Fiat-Shamir heuristic to construct a transcript of the interactive proof. Miners determine the random point $x$ by salting the hash of the previous block with the coefficients of the Sum Check protocol.

The authors go on to describe that the $\text{kOV}$ problem is related to the $\text{APSP}$ problem and the $\text{3SUM}$ problem.

I suspect this work may be a spring-board to other ideas?

**Reference**

**\[BRSV17\]** M. Ball, A. Rosen, M. Sabin, and P. N. Vasedevan. Proofs of Useful Work. 2017

P.S. I'm not sure if my LaTeX is right for KOV, APSP, 3SUM etc.
> 2 votes

---
Tags: complexity-theory, np, hash, proof-of-work
---


title: How is integer factoring not in $P$?

text:
# Question
Title: How is integer factoring not in $P$?
Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\log(n)$... How is that not in $P$? Is there something I'm missing?

# Answer
> 7 votes
One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of the encoding of the input on a Turing Machine (or something closely equivalent).

So the input to integer factoring, as a decision problem, is typically two numbers $n$ and $k$ in $\mathbb{N}$, and the question is whether $n$ has a factor $d \leq k$.

So the magnitude of $n$ is $n$, but the *size of its encoding* may be only $O(\log n)$ (for example, in binary). This is exponentially smaller than $n$ (i.e. if we take $n' = \log\_{2} n$, then $n = 2^{n'}$).

So then the $\sqrt{n}\log n$ "obvious" algorithm runs in time $2^{\frac{n'}{2}}\cdot n'$, which is exponential in the input size.

---
Tags: complexity-theory, factoring, pseudo-polynomial
---


title: Pipeline hazards question

text:
# Question
Title: Pipeline hazards question
i know that resources duplicate is solution to Structure Hazard but what about code scheduling ....
Can code scheduling considered as a solution to Structure Hazard ?
with Example please .

# Answer
Assuming you're referring to how out of order execution can resolve a lack of resources. As resources are used and code is executed temporally, by reordering the code, the usage of resources can be rearranged in time, benefiting execution by a more efficient (less time waiting, more time using) use of resources.

I'm not a big fan of examples but let's suppose two super scalar pipelines want to use resources A, B, C and D, at the same time:

```
time = 0 | A | A
time = 1 | B | B
time = 2 | C | C
time = 3 | D | D

```

The CPU can reorder these instructions

```
time = 0 | B | A
time = 1 | C | B
time = 2 | D | C
time = 3 | A | D

```

Another example: Suppose one instruction pipeline has the following instructions:

```
multiply_then_add
add_then_multiply
do_something_else

```

Then the usage of resources might look like this:

```
time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A |
time = 3 | M |   |
time = 4 |   |   | D

```

where M = multiplier, A = adder, and D = Doing something else. As you can see, the two add instructions back to back are an issue, if they were separated by a gap we could shorten the time taken, and out of order execution can resolve this:

```
multiply_then_add
do_something_else
add_then_multiply

```

```
time = 0 | M |   |
time = 1 |   | A |
time = 2 |   |   | D
time = 3 |   | A |
time = 4 | M |   |

```

Which can be optimised:

```
time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A | D
time = 4 | M |   |

```
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
Can someone help with this $L= \\{a^ib^j | 2i \leq 2j \leq 3i, i\>0\\}$

# Answer
Let me prove a more general theorem.

> For $A \subseteq \mathbb{N}^2$, the language $L(A) = \\{a^i b^j : (i,j) \in A \\}$ is context-free iff $A$ is semi-linear.

One direction is Parikh's theorem. In the other direction, it suffices to show that $L(A)$ is context-free if $A$ is linear (since every semi-linear set is a union of linear sets). Indeed, suppose that $A = (i\_0,j\_0) + \sum\_{t=1}^m \mathbb{N} (i\_t,j\_t)$. Then $L(A)$ is generated by the grammar $$ S \to a^{i\_0} b^{j\_0} \mid a^{i\_1} S b^{j\_1} \mid \cdots \mid a^{i\_m} S b^{j\_m}. $$

A classical result shows that a set is semi-linear iff it is definable in Presburger arithmetic. In particular, if $A$ is the solution set of a system of linear inequalities with rational coefficients (as in your example) then $A$ is semi-linear and so so $L(A)$ is context-free.

In your particular case, ignoring for the moment the condition $i \> 0$, we have $$ A = \\{ (i,j) : 2i \leq 2j \leq 3j \\} = \mathbb{N}(1,1) + \mathbb{N}(2,3). $$ Indeed, clearly $(1,1),(2,3) \in A$ and $A$ is closed under addition, and so $\mathbb{N}(1,1) + \mathbb{N}(2,3) \subseteq A$. In the other direction, suppose that $2i \leq 2j \leq 3i$. Then $$ (3i-2j)(1,1) + (j-i)(2,3) = (i,j). $$ This shows that the following grammar generates your language without the condition $i \> 0$: $$ S \to \epsilon \mid aSb \mid a^2Sb^3. $$ If we bring back the condition $i \> 0$, then we get the decomposition $$ A = \\{ (i,j) : 2i \leq 2j \leq 3j \text{ and } i \> 0 \\} = \\{(1,1) + (2,3)\\} + \mathbb{N}(1,1) + \mathbb{N}(2,3), $$ leading to the grammar $$ S \to ab \mid a^2b^3 \mid aSb \mid a^2Sb^3. $$

In these examples all linear sets were generated by two vectors ("periods"). Indeed, a classical result (following from Caratheodory's theorem; see for example Slide 24 of these slides by Widjaja Lin) shows that every semi-linear set in dimension $k$ (in our case, $k=2$) is the union of linear sets with at most $k$ periods.

If you are interested in the algorithmic side of things, The taming of the semi-linear set is a good starting point.
> 4 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: How to find the closest N to the power of X to the given number?
Let's say we have number 4920 and we want to find the closest $n^x$ to 4920

2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920

The question is, how do we find the closest $n^x$, where $n$ and $x$ are less than 2 digits long? (because $4913^1$ is not what I want)

# Answer
> 1 votes
If $n$ and $x$ are both less than 100, there are only 10,000 combinations to check (including duplicates like $2^4 = 4^2$). That's nothing. You could precompute all of them and then implement the lookup using binary search.

# Answer
> 6 votes
Here is a general solution for the following problem:

> Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$.

Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b \> m$ then there is no point to check any $b\_0 \> b$, hence we only need to check $O(\log m) = O(n)$ many different values of $b$ (we can find the maximal $b$ by comparing $2^b$ to $m$). For each value of $b$, we can find the best value of $a$ using binary search; this takes polynomial time for each $b$, and so polynomial time overall. Finally, we choose the optimal solution among the $O(\log m)$ possibilities.

---
Tags: algorithms, arithmetic, number-theory, integers
---


title: weak Church-Turing thesis

text:
# Question
Title: weak Church-Turing thesis
(weak) Church-Turing thesis states every physically realizable computation device can be simulated by a Turing machine (not necessarily efficiently). (1) Then Does any model that is not physically realizable and cannot be simulated by Turing machine? (2) Is there any evidence for this thesis?

# Answer
You are asking two questions. The answer to your first question, for models stronger than Turing computation, is the field of hypercomputation. The answer to your second question, asking for evidence for the Church-Turing thesis, has been answered on cstheory.
> 3 votes

---
Tags: computability, church-turing-thesis
---


# Question
Title: Is the dynamic programming pairwise alignment algorithm considered greedy?
I'm a freshman in Computer Science and I'm studying bioinformatics sequence alignment algorithms.
My understanding of a greedy algorithm is one that takes the best decision for a particular instance in order to find a general best decision. By that definition, would the basic dynamic programming pairwise alignment algorithm be considered greedy?

# Answer
> 2 votes
No. Rather, the DP algorithm for pairwise sequence alignment1 is an instance of backtracking. What makes it superior to naïve exhaustive search is that

1. it abandons potential solutions as soon as it can prove that it is going to be sub-optimal (each field in the DP matrix considers only the optimal previous sub-alignment), and
2. it computes partial results only once and reuses them — that’s the “dynamic programming” aspect of it.

There are other, greedy algorithms for pairwise sequence alignment. These will first find so-called perfect “seed matches” between a query and a database, and then extend those outwards using one of several strategies. They thus explore locally optimal solutions but aren’t (in general) guaranteed to find a global optimum. This is for instance what the BLAST algorithm is doing.

---

1 By which I’m assuming you mean the Needleman–Wunsch or Smith–Waterman algorithm or some minor variation.

---
Tags: dynamic-programming, bioinformatics
---


title: Do NPDA work in parallel?

text:
# Question
Title: Do NPDA work in parallel?
Assume my language is $$ L= ww^{r}\ $$

Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice here. Now each branch will get the current stack contents and start its operation.

So my question is, do these branches operate in parallel or one after another? We have only one stack and each branch will do push/pop according to its requirement and changes the stack. Even if a branch results in dead end, we need to proceed further. How is a single stack able to manage this scenario, as stack contents are changed by each branch?

# Answer
> 7 votes
The difference between DPDA and NPDA is that in NPDA there may be **more than one** possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one transition. So, computation of a NPDA looks like a tree, i.e., different branches for different computation paths. Computation halts when you reach a "leaf".

You can think of a computation process on a NPDA like (you suggested) running these branches in parallel where **each branch has its own stack**. Each branch may accept or reject input. If **at least one branch halts with accept** then the NPDA accepts that input. Otherwise it rejects.

Alternatively you could think of the computation as breadth first traversal on these branches. There is only one stack. You reuse the stack by restoring its content when you backtrack. You also should remember the position of the head on the input tape and content of the tape. This is the same as you look for the exit from a maze. You try different paths, and when you detect that you hit the dead end you return to the previous position and try different paths.

The latter is suitable for simulation on real computers.

You should also remember that unlike DFAs and NFAs, DPDAs and NPDAs are not equivalent.

# Answer
> 7 votes
That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.

**The genie.** Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

**Hints.** The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

* *Completeness:* if $w \in L$ then there is some hint $x$ which causes the machine to accept.
* *Soundness:* if $w \notin L$ then the machine rejects on all hints.

**Accepting computations.** An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using *snapshots*. A snapshot is a triple $(q,z,t)$, where $q$ is the current state, $z$ is the part of the word which remains to be read, and $t$ is the contents of the stack. We can define a relation $(q\_1,z\_1,t\_1) \vdash (q\_2,z\_2,t\_2)$ which expresses that the machine can reach snapshot $(q\_2,z\_2,t\_2)$ from snapshot $(q\_1,z\_1,t\_1)$ in one step. An accepting computation for a word $w$ (for the acceptance condition of emptying the stack) is a sequence $\sigma\_0 = (q\_0,w,\bot),\sigma\_1,\ldots,\sigma\_N=(q,\epsilon,\epsilon)$, where $q\_0$ is the initial state, $\bot$ is the initial state of the stack, $q$ is an arbitrary state, $\epsilon$ is the empty word/stack, and $\sigma\_{i-1} \vdash \sigma\_i$ for all $i$.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are snapshots and there is an edge from $\sigma$ to $\tau$ if $\sigma \vdash \tau$. An accepting computation is a path from $(q\_0,w,\bot)$ to $(q,\epsilon,\epsilon)$, for any state $q$.

---
Tags: context-free, automata, pushdown-automata, nondeterminism
---


title: Math courses for machine learning

text:
# Question
Title: Math courses for machine learning
I have a few math courses to pick from in my studies, and I would love some insights on which math courses from the following list are the most relevant for machine learning. I will note - to avoid this question being closed on "opinion based" cause, that my question does not involve which math courses I like or interests me, but being objectively as possible - which math courses are the most relevant for machine learning.

This are the following courses I can choose from:

1. Numerical Analysis
2. Ordinary Differential Equations 1
3. Topology
4. Theory of Functions of a Complex Variable 1
5. Linear Algebra 3
6. Number Theory
7. Probability for Sciences

Since I know Linear Algebra and Probability are very important for Machine Learning, I will note that I have already studied Linear Algebra 1 and 2 (which include matrices, linear transformations, linear and bilinear operators, normed vector spaces, eigenvalues and eigenvectors, diagonalization, Jordan form, hermitian spaces, unitary and orthogonal transformations, and some more subjects), while Linear Algebra 3 syllabus' is mainly about groups, isomorphism theorems, Lagrange's theorem, group actions, Sylow's theorems, finitely generated Abelian groups, solvable groups, the symmetric group and free groups.

Also, I already had Probability 101 which is mainly discrete probability and includes basic probability theory, discrete distributions (such as Poisson, binomial, HG and more), random variables, markov's and Chebyshev's inequalities, expected value, variance and covariance, CLT and Markov chains, while the "Probability for Sciences" course has in its syllabus continues distributions, PDF, MGF, convergence of random variables and convergence in probability, the multi-dimensional normal distribution and some more subjects.

I will also note I have studied the following math courses as well: Calculus 1 and 2 and Discrete Math.

Thanks!

# Answer
> 4 votes
By far the most important in that list is probability -- learn as much probability as you can. Numerical analysis might also be of a little bit of use. The others probably won't be directly relevant to most of the practice of machine learning, but hey, become more comfortable with mathematics is probably useful in general.

---
Tags: machine-learning, education
---


# Question
Title: Algorithm to find the optimal strategy to feed your cousin (Long question)
I have a programming problem, instead of describing the whole domain it's easier for me to create an analogy. The numbers I use in this example are completely arbitrary.

Your cousin is coming over later and you must feed him dinner. He will only eat what he randomly decides he wants when he gets to your house and will not tell you ahead of time what that will be. However, you have been given a list of recipes that you know for certain he will choose from.

All of the recipes are soups that are made from one or more ingredients and the recipes call for small, medium, or large cans of each ingredient. There are no rules for how many cans are required or what sizes they can come in, but you don't care about waste so it's fine if you use a can that is larger than the recipe calls for.

Your cousin isn't very strict about sticking to the recipe, in fact, only half of the ingredients have to even be in the pot for him to call the recipe complete!

Unfortunately you have exactly zero of the ingredients needed and you only have time to make a short shopping trip before he arrives. Additionally, the store you're shopping at will only allow you to leave if you have exactly 5 small cans, 4 medium cans and 3 large cans. Once again, you don't care about waste so getting extra, unused cans is perfectly okay.

Since you don't know what recipe you'll be demanded to make, you want to try to be prepared to cook as many recipes as possible, but because of the restrictions on number of cans you can buy you will not be able to buy all of them.

I am attempting, essentially, to find an algorithm that takes the list of recipes and then suggests a shopping list that covers the maximum number of recipes.

**Summary of rules**

* Demanded recipe is random
* You only need to adhere to 50% of the ingredients called for
* You must buy **exactly** 5 large cans 10 medium cans and 20 small cans
* Waste is fine, using cans larger than needed or buying extra cans is okay
* Using larger cans does not constitute completing the recipe more than smaller cans
* For example: A 3-ingredient recipe is still only 33% complete from one can regardless of size.
* You will be asked to prepare exactly one recipe, no more
* Currently there are 25 recipes on the list, but more get added each time your cousin visits!
* There are no recipes with more than 15 ingredients, some have zero ingredients but we just ignore them
* Practically there's probably around 75 ingredients among the recipes

**My attempts**

My first idea was to iterate through the ingredients and rank them on how much they contribute to each recipe. For example, if a recipe calls for 10 ingredients then our ingredient would have 0.1 added to it's score. If another 2-ingredient recipe used that ingredient it would have a score of 0.1 + 0.5 = 0.6

Each ingredient would have a rank for each can size (Small, Medium, Large)

I would then consider each ingredient by summing the size ranks up to a given size. So for example I would add the Small + Medium + Large ranks together and sort the ingredients on that sum to decide which ingredients I would buy large cans of. Then I would remove those ingredients from the list and do the same thing with Small + Medium ranks.

Then I realized if there were 20 recipes with one ingredient in common, but none of the other ingredients were used anywhere else (even among the 20 recipes) then we would have one ingredient with a huge rank which couldn't even satisfy one recipe.

Then I thought it would be good to include a commonality factor into my calculations: An ingredient would also be ranked on the commonality of it's "friends". An ingredient is "friends" with another if they share the same recipes. If an ingredient has low ranking or uncommon friends then it should rank low too.

I just now realized I might be coming at this backwards, maybe I should compare how much the recipes have in common. If a recipe has a lot in common with many other recipes then covering it will probably cover all of the recipes similar to it.

Any ideas on how to find the solution to this? I cannot believe there hasn't been a graph theory problem similar to mine somewhere out there. I just haven't found it yet.

# Answer
> 0 votes
Your problem sounds like the sort of thing that would be NP-complete (though I haven't proven it), so I'd expect there probably is no efficient algorithm that is guaranteed to find the optimal solution. Instead, I'd suggesting looking at Dealing with intractability: NP-complete problems for technique you could try. You'll probably be looking for some kind of heuristic. For instance, you might try simulated annealing.

You could also try expressing this as an instance of integer linear programming and applying an off-the-shelf ILP solver. I don't know if that is likely to work well, though. The resulting system of constraints will be fairly complex, and so might be too hard for ILP solvers. A possible approach to do that would be to introduce zero-or-one variables $x\_{i,s},y\_j,z\_{i,j}$, with the intention that $x\_{i,s}=1$ counts the number of size-$s$ cans of the $i$th ingredient that are purchased and $y\_j=1$ means that the $j$th recipe can be prepared from the purchased ingredients and $z\_{i,j}=1$ means that ingredient $i$ has been bought in sufficient quantity for recipe $j$; then add inequalities to enforce the constraints you mentioned.

---
Tags: graphs, knapsack-problems, game-theory
---


title: Check if given language is CFL

text:
# Question
Title: Check if given language is CFL
Assume language $L$ as follow:- $$ L = \\{ a^n b^x c^m d^y | (n=m) \lor (x=y)\\} $$ Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. But is it possible with "or"?

My approach:- 1. Push all $a$'s to the stack.

2. At $b$ define non deterministic behavior as follow:-

2.1. Assume we are checking for $n=m$.So skip all the $b$'s.

2.1.2.Whenever $c$ is encountered, pop $a$ for $c$.

2.1.3. When $d$ is encountered check if stack is empty, if yes, then accept else reject.

2.2. Assume we are checking $x=y$. So push all the $b$'s to the stack. Now when $c$'s are encountered skip them.

2.2.1. When $d$'s are encountered, count them with $b$'s which are on top of stack.

2.2.2. When input is finished and stack is empty or contains only $A$, then accept else reject.

# Answer
Note that $$ L = \\{ a^n b^x c^n d^y : n,x,y \geq 0 \\} \cup \\{ a^n b^x c^m d^x : n,m,x \geq 0 \\}. $$ Try showing that each of these is context-free individually.
> 1 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: Is data received after transmission immediately stored and can that be recovered?
When I send a message from one device to another, during the process during which the other device is receiving the data, is that data stored temporarily on some place on the device or is it immediately stored on the hard-drive of the device. and while using TCP when you receive an ACK does this mean that that data has been stored on the hard drive or is it stored when everything is received. For example, I am sending an essay to a server which makes a download link for another person and then send that link back to me, for sharing. Now during the process of sending that essay on the server I cancel halfway, so can I determine whether the essay was stored on its main drive or not (just an example).

# Answer
> 3 votes
Briefly, communication between two hosts/peers on a network occurs by means of *network sockets*. Roughly a socket is pair (IP,PORT) of numbers which uniquely identifies a host on a network. So, when a host A sends data to another host B on the network, B listens to a corresponding port for incoming data. Data (**payload**) comes byte-by-byte and when one byte of data riches destination B gets notification. **At this point it is up to the application what to do with data: to store it on the hard drive or in memory.** Nothing is stored in HDD or on some other device by default.

As for "sending an essay to a server" your are talking about file transfer protocols, in particular file uploads. Whether your file was stored on the server depends on the underlying protocol. For example recently people have started talking about resumable file upload protocol.

Your questions say that you should start learning from basic TCP/IP and HTTP protocols, and move towards more advanced and specific protocols depending on your tasks.

---
Tags: communication-protocols
---


# Question
Title: What is the largest possible minimal 3CNF formula as function of the number of variables?
I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

> What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

> In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of **n**, where **n** is the number of variables in the 3CNF formula.

Is it $O(n)$? Is it $O(log(n))$? Is it $O(1)$, but just larger than 8?

# Answer
Chungboom Lee, On the size of minimal unsatisfiable formulas shows that when $k=2$, the answer is $\Theta(n)$, and when $k \geq 3$, the answer is $\Theta(n^k)$. Here $k$ is width of the clauses.
> 3 votes

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: number of subsegments that contain A[i] as the minimum
I've recently been thinking about this problem.

Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A\[i\]$ as their minimum.

To better illustrate the problem, consider the array $A = \[5, 1, 7\]$ and we want to find the number of subsegments containing $A\[1\] = 1$ as their minimum. Clearly the answer is 4 and we can easily enumerate them: $\[1\], \[5, 1\],\[5, 1, 7\], \[1, 7\]$.

What the fastest way to compute the number of subsegments?

# Answer
> 3 votes
You haven't stated what a subsegment is, but I assume that you mean a "contiguous subsequence", that is, $A\[s\],A\[s+1\],\ldots,A\[t\]$. Also, I'm assuming that $A\[i\]$ is still a minimum if there are other equal values (you can easily adapt the algorithm for the other option).

Let $\ell \leq i$ be the smallest index such that $A\[s\] \leq A\[i\]$ for all $\ell \leq s \leq i$, and let $r \geq i$ be the largest index such that $A\[r\] \leq A\[i\]$ for all $i \leq s \leq r$. Then $A\[i\]$ is a minimum of $A\[s\],\ldots,A\[t\]$ iff $\ell \leq s$ and $t \leq r$. Thus there are $i-\ell+1$ options for $s$, namely $\ell,\ell+1,\ldots,i$, and similarly $r-i+1$ options for $t$, for a total of $(i-\ell+1)(r-i+1)$.

You can easily find $\ell,r$ in linear time by scanning left of and right of $i$ (respectively), so this algorithm runs in linear time.

---
Tags: optimization, time-complexity, asymptotics, combinatorics, arrays
---


# Question
Title: creditcard validation - why does nit not fail for 7 digits?
using luhns credit card check algorithm why is digits with 7 length allowed ? for example 1111111 is a verfied credit card number meaningly if it has only six digits its not. this does not look like a credit card number to me, am i missing something ?

go to any online credit card validation site and try 1111111 and see that it returns valid. why ?

I have tried going to the following websites: http://www.dcode.fr/luhn-algorithm and a few others.

# Answer
Luhn's algorithm, as described in Wikipedia, works for any number of digits. It will detect any single digit change and most swaps.

As for an internet website which accepts credit card numbers of the wrong length - the blame should be on the designers of the website who neglected to enforce this restriction, not on Luhn's algorithm, which performs as advertized.
> 2 votes

---
Tags: algorithms
---


# Question
Title: What would "sum types with functions" look like in OOP?
It's fair to summarize classes in OOP as "product types with functions." However, couldn't there be something like "sum types with functions"? How would inheritance work with them?

I'm trying to scout if anybody has considered this question before in language design.

# Answer
The key to remember is that there's a sort of dualism between functional sum types, and OOP implementations of a superclass or interface:

* Sum types require the variants for a type to be specified up front, and for every operation, requires that we specify the operation for each variant. Adding a new operation is easy, adding a variant requires refactoring all functions.
* OOP requires that we specify the operations for a type up front, and each implementation/subclass specifies its own implementation for each operation. Adding a new variant is easy, but adding a new operation requires refactoring in each subclass.

In each case, we have all possible pairs of variants and operations, but we differ on how we group them: all the implementations for variants in an operation together, or all the operations for a variant together.

> It's fair to summarize classes in OOP as "product types with functions."

At its most barebones version, maybe. But this ignores any subtyping structure. Many versions of OOP are much richer, with interfaces being analogous to existential types.

As for the question of "what if we just did sum-types with functions", this would be pretty boring. You would specify a bunch of variants for your type, and then a bunch of operations your type, which would have to specify an implementation for each variant.

This is basically just a normal OOP type with a single member variable that's a sum-type, and a bunch of functions operating on that variable.
> 7 votes

# Answer
Hm, I don't have the points to comment, but are you sure you mean that?

Classes already *are* a sort of sum type: polymorphism means that a variable declared to refer to something of type "A" could instead refer to an object of any of its subclasses B, C, etc. - so this is like a tagged union.

And of course, as you say, objects are also product types, in that in most imperative languages, they're jumped-up record types.

Anyway. If this isn't what you mean, it might be worth looking in one of the texts on theory of OO languages to see if what you're after has been covered – perhaps Abadi and Cardelli's Theory of Objects might have something.
> 4 votes

---
Tags: programming-languages, type-theory, object-oriented
---


title: Dynamic Programming to Maximize Profit

text:
# Question
Title: Dynamic Programming to Maximize Profit
I have this problem to resolve in dynamic programming:

> An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are in different places, there are different points for selling the ice cream. It was estimated the profit (in monetary unit) that could be obtained in each store:

$$ \begin{array}{c|lcr} N refrigerators & \text{store1} & \text{store2} & \text{store3} & \text{store4} \\ \hline 1 & 4 & 2 & 6 & 1 \\ 2 & 6 & 6 & 12 & 4 \\ 3 & 10 & 8 & 14 & 8 \\ 4 & 12 & 10 & 18 & 16 \\ 5 & 14 & 12 & 20 & 20 \\ 6 & 16 & 16 & 22 & 21 \\ 7 & 18 & 20 & 22 & 24 \end{array} $$

The problem asks to find the working scheme that maximizes the financial return.

As dynamic programming aims to reuse the code I know that it is necessary to use a recursive function, but when analyzing the problem I assumed that my answer field is in a matrix where the lines are referring to the number of refrigerators and the columns the stores.

Then I assumed that $M(i, j)$ is my function that returns a monetary value, assuming that $i$ is the number of refrigerators, ranging from $1 \le i \le 7$, and $j$ is a particular store, ranging from $1 \le j \le 4$.

I also assumed that my function would have 4 calls of this same function $M(i, j)$, because there are 4 stores to divide 7 refrigerators:

The equation would be:

$$MAX \\{ M(i, 1) + M (i, 2) + M (i, 3) + M (i, 4)\\}$$

Where $\sum\_{i=1}^4 i \le 7$

As a base case of recursion I put this:

$$M(0, 1) + M (0, 2) + M (0, 3) + M (0, 4) = 0$$

But my problem is not knowing how to treat this problem recursively. Maybe I'm doing the wrong analysis, too. Every help is welcome.

# Answer
> 1 votes
In this particular case, you can just go over all possibilities.

The dynamic programming approach is to compute recursively the maximal profit that can be obtained from using $x$ refrigerators in the first $y$ stores (and not using any in the other stores). I'll let you fill in the missing details.

---
Tags: optimization, dynamic-programming
---


# Question
Title: How do you represent LISP as mathematical / logical model?
I asked this in stackoverflow, but the question probably fits here better.

This question arose from the objection that LISP is regarded as a functional language with some simple principles, namely functions, variables, and operators that roughly correspond to predicates, propositional variables, and connectives in logic respectively.

How would you define recursive structure and "data is a function is a data" paradigm central in LISP as a mathematical model? How about list processing feature? Can we derive LISP from simple mathematical foundations starting from propositional logic up to some specific factored logic?

Surely there must be a model, not only for LISP, but many similar "old" languages. So, I'd like to know, what are the necessary concepts of mathematics to define LISP-like language.

Point is not on what paradigm LISP fits the best, but to find out the simplest mathematical model for the language in question.

---

Lately, I found this paper of McCarthy (1960) which may answer the question: http://www-formal.stanford.edu/jmc/recursive.pdf

Logic, arithemic and automata by Church (1962) also seems a useful source: http://www.mathunion.org/ICM/ICM1962.1/Main/icm1962.1.0023.0058.ocr.pdf

# Answer
"Old" programming languages like Fortran, Cobol and LISP arose *before* serious mathematical theory of programming languages was developed. They *inspired* the development of such theory, but are full of idiosyncracies and features which from a mathematical point of view can best be described as "warts". However, each of the old languages *in essence* has a mathematical core. We can extract their cores and see what mathematical models those have.

For LISP the core would be a small subset of Scheme. Let us focus just on the list processing part, and forget about the fact that in LISP and Scheme one can change state with `setq` and the like.

A small core for LISP could contain the atoms, S-expressions and functions, by which we mean some basic functions, $\lambda$-abstractions, and recursive functions. There are several ways to model this much of LISP, but perhaps the neatest is by domain theory.

Consider the following simplified statement about (a core of) LISP. Every value is

1. *either* an atom (a literal),
2. *or* a cons,
3. *or* a function.

Let us try to express this idea mathematically. We should find a set $D$ of *LISP values* which

1. contains the set $A$ of all atoms (whatever they are)
2. contains $D \times D$ because every cons is a pair of values (car and cdr)
3. contains $D \to D$ because "functions are data"

We can express this idea as a requirement that $$A + D \times D + (D \to D) \subseteq D.$$ Unfortunately, this is not possible because $D \to D$ is larger than $D$, unless $D$ contains just one element (but there are many atoms).

However, there is a way out: the set $D \to D$ of functions is larger than $D$ *only* if we take *all functions* -- but we only need to consider the *computable* functions, or some slightly larger set of them. Indeed, as was shown by Dana Scott a long time ago, we should look for a *space* $D$ (rather than a *set*) and then take $D \to D$ to be the space of *continuous functions* (because every computable map is continuous). As it turns out, there are several kinds of "spaces" that we could use, all of which have in common that they capture the idea of *information content* and *information processing*. I cannot go into technical details on how this is done, but you can read about domain theory to find out more.

Let us just think about what $D$ must contain. Of course, it contains various atoms, includnig an element corresponding to `nil`. Then, it contains all finite lists of elements, since a list `(x1 ... xn)` is just a lot of nested pairs `(x1, (x2, ..., (xn, nil))`. Next, it contains lot and lots of functions: anything that can be defined by a `lambda`, and with a bit of care also anything that can be defined by recursion.

In summary, the answer to your question is that *the mathematical essence of LISP is a space $D$ which contains the atoms, its own product $D \times D$ and its own function space $D \to D$*.

The stuff about logic and propositional connectives, you should forget that on the first round of studying mathematical models of LISP. Maybe come back to it later, and look up something like Curry-Howard correspondence and realizability.
> 6 votes

---
Tags: logic, functional-programming, mathematical-foundations, lisp
---


# Question
Title: Proving that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$
> Prove that for every two positive functions $f(n),g(n)$: $$ \max(f(n),g(n)) = \Theta(f(n)+g(n)). $$

---

I've just started data structures and I barely understand it, so please be gentle with me.

# Answer
This follows from the inequality $$ \frac{a+b}{2} \leq \max(a,b) \leq a+b. $$ To prove this, assume that $a \leq b$. You need to show that this implies that $$ \frac{a+b}{2} \leq b \leq a+b. $$
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Planar Embedding with Some Nodes Constrained
I've read about basic planar-graph embedding and about embedding a planar graph onto a set of fixed points, but I was wondering how one might constrain the locations of some nodes—perhaps to a set of points—while allowing others complete freedom.

Is this achievable with a current popular algorithm, or with minor modification thereto? I guess the nature of the problem would lend itself better to grid-based embeddings, right?

I'm entirely new to graph theory, so it's possible the answer is obvious to those familiar with the field. I didn't see anything about it while searching.

# Answer
This was meant to be a comment but it was a bit too long, sorry!

There is a well known algorithm to draw a planar graph, namely Tutte's drawing algorithm. The input graph is assumed to be 3-connected and planar. The idea of the algorithm is to fix the position of vertices of a face in convex position and from those coordinates deduce the positions for the rest of the vertices. The resulting drawing being a planar drawing of the input graph. Perhaps you can find more about this at \[\].

With respect to grids, there are a couple of well known algorithms for drawing planar 3-connected graphs. One is Schnyder's algorithm (through the a Schnyder wood decomposition of the edges), and the canonical ordering algorithm (through a partition of the vertices of the graph). Both of these algorithms run in $O(n)$ time and produce drawings in an $O(n)\times O(n)$grid, where $n$ is the number of vertices of the input graph. At \[\] you may find an overview of these two algorithms for the case of planar triangulations. You could even go to references \[4\] and \[9\] cited there for the original papers. It is worth noting that these algorithms have been generalized to work on 3-connected planar graphs as stated above.

Are you thinking about drawings subject to more specific constraints?
> 1 votes

---
Tags: graphs, planar-graphs
---


title: Minimum difference of sums

text:
# Question
Title: Minimum difference of sums
So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is:

Given and two integers $n$ and $k$ and an array $A$ containing $n$ pairs of integers of the form $(a, b)$ and $d$ defined as $d = |\sum\_{x \in E} x\[1\] -x\[0\]| $ where is $E$ is a subset of $A$ containing exactly $k$ elements. Find the minimum value of $d$.

To illustrate the problem, consider $n = 3$, $k = 2$, $A = \[(2, 1), (0, 2), (1, 2)\]$.

The minimum value of $d$ is $0$. We can pick $E = \[(1, 2), (2, 1)\]$ containing $k = 2$ values of $A$ then $d = |(1 - 2) + (2 - 1)| = |0| = 0$.

I tried to solve this problem but only came up with the brute force solution which is terrible in terms of time complexity.

> How can one solve this problem efficiently ?

# Answer
I'm unable to add comments but I think this problem can be simplified to:

```
B = []
for pair in A:
    B.append(pair[0] - pair[1])

min_sum(B, k)

```

`min_sum` returns k elements that add up to give the smallest number possible (absolute value). This (at least to me) feels easier to work with.
> 2 votes

---
Tags: algorithms, optimization, time-complexity, asymptotics
---


# Question
Title: How to calculate whether a parenthesis string is valid using a 2-tape Turing machine?
If I have a language over alphabet $\Sigma=\\{(,\[,\],)\\}$. How can I find out if a tape has a valid (matching) parentheses structure in linear time?

So far, my attempt is as follows:

* state 0: accept ( or \[ *i.e. no open parentheses*
* state 1: accept ), ( or \[ *i.e. a ( has occurred previously*
* state 2: accept \], ( or \[ *i.e. a \[ has occurred previously*

The problem with this setup is that I won't know how many ( or \[ has occurred previously. One idea was to store how many occurrences of open parentheses of each kind on the second tape, but this would potentially require an infinite tape alphabet. So it seems as if I'm approaching the problem the wrong way.

How can I create a Turing machine that wouldn't need to store the amount of open parentheses while still being able to accomplish this in linear time?

I looked at this question already, but couldn't figure out how this would be applicable to multiple types of parentheses and still be done in linear time.

Any input would be much appreciated!

# Answer
> 1 votes
As others have pointed out, you can use a stack to check for matching parentheses. Such manipulation is the base idea of the shunting yard algorithm by Dijkstra.

# Answer
> 0 votes
Hint: use the second tape to store the stack of open brackets and parentheses you've seen. Each time you see a close, manipulate the stack appropriately.

---
Tags: turing-machines
---


# Question
Title: Residual graph of a graph with bidirectional edges?
Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$.

$e.g:$

In the example, there is an edge going from $C$ to $A$ and viceversa.

So, my question is, what would be the way to model this graph with a residual graph?

# Answer
The *residual graph* is not a graph modeling method. It represents how we can change the flow on edges of a graph $G$ in order to increase the total flow when we compute the maximum flow.

The *residual capacity* used when you construct the residual graph is defined as $$ c\_f(u,v) = \begin{cases} c(u,v) - f(u,v) & \text{if $ (u,v) \in E$} \\ f(v,u) & \text{if $ (v,u) \in E$} \\ 0 & \text{otherwise} \end{cases}\ $$

So, we cannot have both $(u,v)$ and $(v,u)$ in $E$ even though the *antiparallel edges* do not contradict the main network flow properties.

Your graph contains antiparallel edges which you should get rid of before you run a maximum flow algorithm on that graph, e.g., Ford-Fulkerson algorithm.

You could transform this graph into equivalent one with no antiparallel edges as following. You choose one antiparallel edge and "split" it into two edges. For example take $AC$ and introduce a new vertex $F$ and two new edges $AF$ and $FC$ with weights equal to $5$, i.e., $w(AF)=w(FC) = 5$. Similarly for every pair of antiparallel edges in the graph.
> 2 votes

---
Tags: graphs, network-flow
---


# Question
Title: Why we can't use non-deterministic turing machines in this case?
Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning is not working.

Problem Given a context free grammar $G$, does there exists a word $w∈Σ^∗$ such that $w^4∈L(G)$ ?

My reasoning: Lets show Turing machine which decide this problem. Let machine guesses some word $w$ (it is possible because word is finite and $Σ$ is finite) and check if (using CYK algorithm) $G$ generates $w^4$.

I totally don't understand why this approach doesn't work. After all, non-determinism is about guessing...

# Answer
> 6 votes
Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In other words, the TM always halts.

In your approach the TM machine has to guess infinitely many strings and check if their forth power belongs to $L(G)$. A nondeterministic Turing machine cannot check infinitely many strings in finite amount of time.

Decidability problems efficiently solved by non-deterministic Turing machines are also solved by deterministic Turing machines. In other words, their computational powers are equivalent.

---
Tags: complexity-theory, turing-machines, nondeterminism
---


# Question
Title: Can two minimum spanning trees for a same graph has different number edges?
(1) Let's say $T\_1$ has $r$ number of edges and $T\_2$ has $s$ number of edges; where $r \ne s$ but two trees has same weight since they both are MST.

I kind feel this kind not be true because to span $n$ vertices with minimum number of edges, we need $n-1$ edges. so MST must have at least $n-1$ edges; if some MST has more than $n-1$ edges, then there must exists a cycle which leads to non-MST.

However, I don't know how to show that if the number of edges is greater or equal to the number of vertices of an an undirected, connected graph $G$, then $G$ has a cycle.

What if the graph is directed? Is this hold as well?

Any hint?

# Answer
> 4 votes
The answer is no. When running an algorithm for finding MST, It is first of all a tree, it has |v| - 1 edges $exactly$.

If there are more than |v| - 1 edges, than there're two vertices that their path isn't simple, which is simply shown with induction. Meaning if there's a path from s to t with more than |v| - 1 edges, one of the vertices will be repeated.

---
Tags: graphs
---


title: Reduction from Clique to something else

text:
# Question
Title: Reduction from Clique to something else
**Given** $G(V,E)$ and $k$. Is there a clique with size $k$?

**Given** set $X = \\{x\_1,x\_2,\dots,x\_n \\}$, and collection $A = \\{A\_1,A\_2,...,A\_n\\}$ of sub-sets of $X$ and $k$. Are there are $k$ different elements in $A$, that every two of them has intersection that isn't empty? For example $A\_1 = \\{ x\_1,x\_2,x\_3 \\}$, $A\_2 = \\{x\_4,x\_5,x\_1 \\}$ so their intersection is $x\_1$ and its valid, but it should be applied for every two $A\_i,A\_j$ in $A$.

**Prove:** That unnamed problem (which surely has a name) is NP-Hard.

**The reduction is..**

$X=E$, and every $A\_i$ in $A$ is composed of edges that are connected to vertex $v\_i$.

I can't understand the reduction, can someone explain why it works please?

# Answer
$X = E$, so it remains to define the collection $A$. For each vertex $v\_i$ in $V$ create $A\_i$ as following: for each edge $x\_t$ incident to the vertex $v\_i$, add $x\_t$ to $A\_i$. Thus the edge $x\_t=(v\_i, v\_j) \in E \Leftrightarrow A\_i \cap A\_j = \\{x\_t\\}$, and every pair $A\_i, A\_j$ has at most one common element. So, if there are $k$ different elements in $A$ such that every two $A\_i, A\_j$ of them has non-empty intersection which is exactly the edge between vertices $v\_i$ and $v\_j$, then these $k$ vertices are pairwise connected meaning that they form a clique.
> 1 votes

---
Tags: algorithms, np-complete, reductions, np-hard, clique
---


# Question
Title: Reachibility between first and last layer in grid graph in logspace
I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $0s$ and $1s$, the undirected edge exists between two $0s$ or $1s$ - one the left, right, up, down. Path can contains only $0s$ or only $1s$.

For example in following graph there exists such path:

```
0 0 1 0
0 0 1 1
0 0 0 1
0 0 0 1

```

For following there is no such path

```
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

```

How to prove it ?

# Answer
> 2 votes
I can't post a comment, which would be more appropriate:

Reingold's result gives a logspace algorithm, but reachability on undirected grid graphs was show to be in $L$ by Blum and Kozen about 30 years prior:

M. Blum and D. Kozen. On the power of the compass (or, why mazes are easier to search than graphs). In IEEE Symposium on Foundations of Computer Science (FOCS), pages 132–142, 1978.

# Answer
> 1 votes
Your problem is an instance of USTCON, which is known to be solvable in log space, thanks to a result of Omer Reingold:

Undirected connectivity in log-space. Omer Reingold. Journal of the ACM, vol 55 no 4, Sept 2008.

Thus, that paper describes how to build a logspace deterministic Turing machine that does what you want.

---
Tags: complexity-theory, graphs, turing-machines, space-complexity
---


title: How can I improve this RL algorithm?

text:
# Question
Title: How can I improve this RL algorithm?
This is the task: I have a unitary target matrix $T$, to decompose using matrices from a fixed (finite) universal set $\\{M\_i\\}$, e.g. $T = M\_6M\_3M\_9M\_0$. The set is universal in the sense that one can reach any unitary with by combining its elements appropriately.

I wrote an RL algorithm with a policy network that I feed with the target $T$ and with the current "state" (i.e. the current product of the matrices that the policy chose), which returns the index of which matrix to pick next. In pseudocode, this is what I wrote:

`reward = 0
 state = Identity_matrix
 chosen_indices = []
 for(i=0,max_episode_length,i++):
 prob_dist = policy(state,T)
 k = random_int(prob_dist)
 state = state * M[k]
 reward -= 1
 if ||T-state|| == 0:
 reward += 100
 end_episode()
loss = discounted_rewards * cross_entropy([prob_dist],[one_hot(k)])
minimize(loss)`

I repeat this loop for several random examples of $T$ of which I know the decomposition. But, even if I limit $T$ to be a *single* matrix from the set, the policy learns a couple of them and then it stops learning, i.e. when I pick a new $T$, the average episode reward remains around zero.

I tried fiddling with the learning rate, the discount factor, the width of the policy network, nothing seems to make things work. What am I doing wrong?

# Answer
> 1 votes
There's no reason to think that reinforcement learning would be effective here. Indeed, the surprise would be if it *did* work! Machine learning isn't a magic silver bullet. I wouldn't expect it to be of any assistance here; the problem relates to deep questions about the structure of the general linear group, which might be quite challenging for your policy network to learn.

Your problem is known as the membership problem for the general linear group, which might be hard (i.e., no efficient algorithm is known), depending on which field you are working over. See https://cstheory.stackexchange.com/q/38000/5038. If we take $T=0$ and are working with $n \times n$ matrices, this is called the matrix mortality problem; it is undecidable for $n \ge 3$. See also https://en.wikipedia.org/wiki/List\_of\_undecidable\_problems#Problems\_about\_matrices. So, in the general case, your problem is undecidable.

Obviously, you shouldn't expect your approach to successfully solve an undecidable problem.

---
Tags: algorithms, machine-learning, reinforcement-learning
---


# Question
Title: What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?
Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.

So I do not see any practical use-cases to prefer unbalanced tree variant of Tree Sort algorithm - Tree Sort with balanced tree seems to be a clear winner on all accounts.

Is my conclusion correct? Is Tree Sort algorithm with balanced tree is always the best choice (when Tree Sort is applicable generally)?

In what cases Tree Sort algorithm with unbalanced tree can be better in some respect?

# Answer
The advantages of unbalanced trees over balanced trees in practical situations are little to none. A large number of predefined algorithms/ data structures that many programming languages use implement a variety of the Tree Sort algorithm in order to keep time complexity of emplacement and retrieval of data to a minimum (keeping in mind that space complexity stays the same). Such varieties are AVL trees and Red-Black trees.

For instance, in STL (Standard Template Library in C++), structures such as map/ multimap, set/ multiset implement a BST as to keep the time factor to a minimum value.

An example of usage of an unordered tree (although not a binary tree) is a tree used to represent TRIE structures. You can find more about these from Wikipedia or Geeksforgeeks.

Hope this was helpful!
> 1 votes

# Answer
The big hurdles with self-balancing trees is that there *can* be a significant amount of overhead if implemented poorly. You don't have this issue in unbalanced trees because it's that simple, you insert, then they stay unbalanced.

With that being said, the difference comes down to the input.

If your input is sorted or almost sorted, as the wiki article says, it will result in a worst-case or bad-case tree which can result in the algorithm being worst-case $O(n^2)$ on an unbalanced tree. This is the scenario (almost sorted input) where you would probably want to use balanced trees.

However, if your input is sufficiently shuffled, then an unbalanced tree would still allow the algorithm to run in expected $O( n \log n)$. This is because we would be creating a Random Binary Search Tree. The expected search length to a node would be $O(\log n)$, thus allowing us to achieve expected $O(n \log n)$ for all insertions.

If you're stuck with a poorly implemented self-balancing BST, then perhaps a light-weight unbalanced tree paired with a good shuffle of the input could be more practical for you.

I haven't done it myself, but I would recommend comparing these two strategies via implementation and compare some statistics. It would probably be interesting.
> 0 votes

---
Tags: sorting, binary-trees, search-trees
---


# Question
Title: Minimum sum of distance from entrance gate
Assumes we have N position, and 3 entrance gate. For example 10 position:

1--2--3--4--5--6--7--8--9--10

For each entrance gate, there is some people waiting to enter and fill positions, first number is position of gate, associated with chair(front of what chair) and second number is number of people to enter:

5 -\> 4

6 -\> 2

10 -\> 2

If each people seats on chair front of gate, it's cost is 1, for every chair in right or left, the cost increase by 1. What is minimum total sum of cost of people distance to their gates? For example:

10 (number of chairs)

4 5 ( gate front of seat 4 with 5 people)

6 2 (gate front of seat 6 with 2 people)

10 2 (gate front of seat 10 with 2 people)

Minimum cost is 18. The seats cost is is:

4 3 2 1 2 1 2 0 2 1

Zero means nobody sits on chair 9.

For above example number of gate associated with each people is:

1 1 1 1 2 2 1 0 3 3

Another example:

10

8 5

9 1

10 2

Answer is 24 and positions are:

0 0 7 5 4 3 2 1 2 1

And number of gate associated with each chair is:

0 0 2 1 1 1 1 1 3 3

What algorithm do you propose?

# Answer
I will try to give a solution. Tell me if I am mistaking anywhere.

First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill chairs from start. then next gate starts where 1st gate stopped. I leave it to you to check that this is the optimal solution.

Second observation : We can use dynamic programming here and start removing chairs. (Here I must say I am sorry as my notations might not match with general notations but I will try my best)

Let us denote the first problem as $f(10,(4,5),(6,2),(10,2))$. 10 is number of chairs, rest are ordered pairs stating number of gate and number of people. Now we will start removing chairs. There are 4 cases : chair is removed before 1st gate or between 1st and 2nd gate or 2nd and 3rd gate or after 3rd gate.

Now we can make the following observation : $f(10,(4,5),(6,2),(10,2))=\min\[f(9,(3,5),(5,2),(9,2)),f(9,(4,5),(5,2),(9,2)),f(9,(4,5),(6,2),(9,2))\]=\min(19,20,18)=18$ (Note that there are 3 cases here as the 4th case doesn't make sense.)

Here as there are 9 people we get the result (of $f$ using the first observation) from here. This is how you can do the problems. There might even be more gates you just have to generalize the function.

Did you understand what I tried to do?
> 2 votes

# Answer
Given a set $G$ of gates, let $C(G)$ be the total cost of people whose position is at most $\max G$ given that $G$ is the set of gates.

For every $i,j$, determine $a(i,j) = \min \\{ C(G) : |G| = i, \max G = j \\}$. Use dynamic programming to compute $a(i,j)$, and use this array to solve your problem.

(There are some details missing here – this is on purpose.)
> 1 votes

---
Tags: algorithms, dynamic-programming, scheduling, backtracking
---


# Question
Title: Is this possible to solve boolean satisfiablility by using karnaugh maps to simplify the whole given boolean formula by simplifying subformulas?
Building karnaugh map for the whole given boolean formula always costs Θ(2n) both time and space complexities, where $n$ is the number of boolean variables in the given boolean formula.

It is recommended to do this if $n$ is small, but if $n$ is large, then practically this is not possible to build karnaugh map for the whole given boolean formula, **but** this is still possible practically to build karnaugh map to some subformula, that contains less and few boolean variables.

In 3SAT, the given boolean formula is always conjunctive normal form, where each clause in the given boolean formula is disjunction of at most 3 literals.

It is practically possible from the given 3CNF formula, to choose 5 clauses arbitrarily and build for them karnaugh map.

For 5 clauses, the number of possible different boolean variables is at most 15, so the size of the karnaugh map is at most 215=32768, which is constant.

But of course it is practically to build karnaugh map for more than 5 clauses as long as there is no too many boolean variables in the boolean subformula.

Let's restrict that the number of boolean variables in the subformula is at most 16, so the size of the karnaugh map is at most 216=65536, which is also constant.

That way it is possible to minimize larger subformula to smaller formula, which suppose to be equivalent, because they have the same truth table and thus replace the subformula with it's minimal equivalent.

Do this for each subformula and that way gradually minimize the whole boolean formula.

If the boolean formula has been simplified to the constant $\bot$, then it is unsatisfiable.

Otherwise it is satisfiable.

If subformula was simplified to $\bot$, then it is unsatisfiable and this implies that the whole given boolean formula is unsatisfiable too.

For instance:

Suppose that the algorithm found the following subformula contained in a boolean formula of 1000 boolean variables and 10000 clauses:

$(x \lor y \lor z) \land (\lnot x \lor y \lor z) \land (x \lor \lnot y \lor z) \land (\lnot x \lor \lnot y \lor z) \land (x \lor y \lor \lnot z) \land (\lnot x \lor y \lor \lnot z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor \lnot z)$

Building karnaugh map for it and use it to minimize this subformula simplifies it to the constant $\bot$, thus the input boolean formula is unsatisfiable, and the complexity to do the last step was very good, because this boolean subformula contains only 3 different boolean variables, no matter that in the input boolean formula n=1000, and building karnaugh map for 3 boolean variables is fine! The size of the karnaugh map is only 23=8, not 2n=21000.

Also if the found subformula is:

$$(x\lor y\lor z)\land(x\lor y\lor\overline z)\land(x\lor\overline y\lor z)\land(x\lor\overline y\lor\overline z)\land(\overline x\lor y\lor z)\land(\overline x\lor y\lor\overline z)\land(\overline x\lor\overline y\lor t)\land(\overline x\lor\overline y\lor\overline t)$$

Building karnaugh map for it and use it to minimize this subformula simplifies it also to the constant $\bot$, thus the input boolean formula is unsatisfiable, and the complexity to do the last step is still good, although now it takes twice more resources than the previous subformula, because the subformula now has 4 boolean variables, rather than 3, but building karnaugh map for 4 boolean variables is not bad too! It only took 24=16 matrix cells rather than 2n=21000.

But iterating through subformulas and building karnaugh maps for them, is not in order to find one, that can be simplified to $\bot$, but the current subformula can be satisfiable, and cannot be simplified to $\bot$, but it's simplification can much help simplifying the whole input boolean formula a lot!

Suppose that the algorithm found the following boolean subformula:

$(x\lor y\lor z)\land(x\lor y\lor\overline z)\land(x\lor\overline y\lor z)\land(x\lor\overline y\lor\overline z)\land(\overline x\lor y\lor z)\land(\overline x\lor y\lor\overline z)$

Building karnaugh map for it, which costs 23=8 by the way because it has only 3 boolean variables, and then use it to minimize it, the subformula is not simplified to $\bot$, because it is satisfiable, but it does simplify to $x \land y$.

This is great! Now you know that the input boolean formula is satisfiable if and only if x=T and y=T, so if the algorithm tries to find satisfying assignment, then it needs to set both x and y to true and now you have eliminated 2 variables from the input, and now you remain n-2 boolean variables left, and all clauses that contain either x or y are satisfied and removed from the input boolean formula. Now the boolean formula is much simpler than before!

I didn't prove it, but I think that deterministic algorithm to simplify huge boolean formula with karnaugh map**s** gradually in steps, can solve the boolean satisfiability problem in polynomial time, but my conjecture has not been proved yet.

So my question is:

Does my conjecture correct?

How can it be either proved to disproved?

# Answer
"arbitrary chosen" in a NP problem where the followup results in a P algorithm typically means that the choice matters *a lot* and trying them all and backtracking over bad choices looking for the result is what pushes the algorithm out of P.

In addition it is possible to create a subformula that you cannot simplify that way. For example a formula that is only true if exactly 1 out of n+1 variables is true. You cannot simplify that by only looking at n variables.

Which means that there are inputs that will not be solvable with that method.
> 6 votes

---
Tags: algorithms, logic, satisfiability, propositional-logic, karnaugh-map
---


# Question
Title: how to express an intertemporal implication constraint in integer linear programming (ILP)?
I want to express the following locigal expression in an IP:

$$x\_{di} \wedge x\_{d'j} \Rightarrow \sum\_{\substack{d'' \in D\\ i \< k \<j}} x\_{d''k} = \sum\_{i\<k\<j} a\_{k} \ \forall \ d, d' \in D, i,j \in T, i\<j$$

where $x\_{dt}$ is a binary decision variable ($x\_{dt} \in \\{0,1\\}$) and $a\_{k}$ is a binary parameter.

The meaning should be as follows: $T$ represents a set of timeslots. Whenever something happens at timeslots $i$ and $j$ (i.e. $x\_{di} = 1$ for some $d$, $x\_{d'j} = 1$ for some $d'$, $i\<j$), then there should also something be happening at all timeslots inbetween $i$ and $j$, but only if at timeslot $t$ something can actually happen ($a\_t = 1$, otherwise $a\_t$ is $0$).

Can anyone tell me how to do this? Thanks in advance!

# Answer
Base yourself on the fact that $x\_{d,i} \land x\_{d',j} $ happens iff $ x\_{d,i} + x\_{d',j} =2 $.

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i\<j, \sum\limits\_{d'' \in D \\ i\<j\<k} x\_{d'',k} \leq \sum\limits\_{i\<j\<k} a\_k + (j-i)(2-x\_{d,i} - x\_{d',j}) $

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i\<j, \sum\limits\_{d'' \in D \\ i\<j\<k} x\_{d'',k} \geq \sum\limits\_{i\<j\<k} a\_k + (j-i)(x\_{d,i} + x\_{d',j} - 2) $

Check these equations in two cases : $ x\_{d,i} + x\_{d',j} =2 $ and $ x\_{d,i} + x\_{d',j} \< 2 $

Depending on your $a\_k$ and problem, you may get a better multiplicative constant than $(j-i)$. If you can, do it, otherwise the continuous relaxation is going to suck.
> 0 votes

---
Tags: optimization, integer-programming
---


# Question
Title: Someone explain the venn diagram for the logic equation A*(B+C)
So, I am studying logic circuits and how to prove them with Venn diagrams. When drawing a Venn diagram for the equation A\*(B+C) I figured it would look something like this:

But according to the answer key, and wolfram alpha, it looks something like this:

Can someone explain why this is? Because doesn't A\*(B+C) simplify to A*B + A*C, which would only be the two shaded regions?

# Answer
> 3 votes
You're absolutely right that $A\times(B+C) = AB+AC$. This means that the formula is true whenever one *or both* of the following hold:

* $A$ is true and $B$ is true;
* $A$ is true and $C$ is true.

Note that the first case doesn't say anything about the value of $C$ – it could be true or false. Similarly, the second case doesn't require anything about $B$. If $A$, $B$ and $C$ are all true, we're in both cases, so the formula is true.

# Answer
> 3 votes
$(B+C) = B\overline{C}+\overline{B}C + BC$

and A with that and you get:

$A\*(B+C) = A\*(B\overline{C}+\overline{B}C + BC) = AB\overline{C}+A\overline{B}C + ABC$

Remember that OR is the *union* and AND is the *intersection*.

---
Tags: logic, circuits
---


# Question
Title: Someone explain the Venn diagram for the logic equation (A+B)(B+C)
I posted a similar question here, however I have another question regarding Venn diagrams and logic circuits...

In this problem:

$$(A+B)(B+C)$$

Wouldn't the Venn diagram look something like this?

Because it simplifies to $B + AC$? And you can either have the $B$ region, the $AC$ region, or both?

However, apparently it's supposed to look something like this:

Which I don't understand... Because by the logic that you have $AB$ and $BC$, couldn't you justify saying that you can also shade in $A$, or shade in $C$ (by themselves)?

OR, does saying $A$ mean you shade in EVERYTHING that contains $A$? And only don't shade in the intersection if you had something that said $A * \overline{B}$?

# Answer
> 2 votes
The misunderstanding here is the same as in your previous question. If $B$ is true, the formula is true whatever the values of $A$ and $C$ are. This means that the whole of the $B$ circle needs to be shaded. Shading just the part at the top corresponds to saying "The formula is true if $B$ is true and $A$ and $C$ are both false." That is certainly true, but it's not the whole story.

For example, your proposed shading says that the formula is false if $A$ is true, $B$ is true and $C$ is false. But the formula is true in that case! You must shade *every* region of the diagram that makes the formula true. In this case, that means every region in the $B$ circle, and also the intersection of the $A$ and $C$ circles. (Corresponding to, "The formula is true if $B$ is true, or if $A$ and $C$ are true, or both.")

---
Tags: logic, circuits, karnaugh-map
---