Analysis of komi values for increasing Go board sizes and agents strength Komi is the additional number of points given to the non-starting player in the game of Go.

For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it was lower, even 2.5 points.

A question arises: what value it should be so that it is a fair game?
Draws allowed.

(This handles the unlikely to me case, in which Go is already fair, without komi. Then one would just discover that komi should be 0. So, I'm  not assuming that Go without komi is unfair)

The following idea came to my mind:

Let's take e.g. 5x5 board and an agent A. Let it self-play many games, plot the average of points won by the starting player in the end of the game, stop simulations when the value converges.

Do the same for 6x6, 7x7 board and so on up to 19x19 (or further).

So, for a given agent A, we will have a list of mean scores for a starting player on increasing board sizes, e.g. [25, 14.2, 9.6, ...], meaning that on a 5x5 board, on average, the first player wins with 25 points. On 6x6 board, on average, with 14.2 points, and so on. These could be the komi values.

Now, maybe the values in the list will be always decreasing. Maybe they converge to some value as the board size grows. Is it already described somewhere?

The values will probably depend on the agent A. Maybe one could also find a relationship between the strength of the agent A and the values in the list. E.g. maybe the stronger the agent, the values decrease slower.

So, one could start with a weak agent. See what values in the list it produces. Then, improve agent A (using e.g. some reinforcement learning algorithm or giving more time to the search) and produce another list of mean values. And so on.

Maybe the variance of results (or some other function) could be a nice measure of how far the current agent is from the optimal one (because the optimal one vs optimal one will always result in exactly one outcome, variance 0). So e.g. maybe agent who has scores vs himself in [-2; 2] is closer to the optimal one than the agent with scores in [-20; 20].

Say for the weakest agent A the list would be [25, 14.2, 9.6, ..., 6.6] and for the strongest agent A (ideally this agent would play optimally) [25, 18, 14, ... 8.2]. Now one knows that the sensible komi for 19x19 is in the range of 6.6 and 8.2.

My questions are:

1) Have you seen something similar done before? I would be happy to read. I've read Solving Go for Rectangular Boards, which solves Go up to 5x5. If such analysis wasn't described, I could do one out of curiosity.

2) Do you see some problems, refinements or other interesting things to check?

From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (see Tablebases, Fermat, Knights and Knightmares - you might need access to ICGA Journal). Optimal solutions frequently destroy any intuition about a game. I expect that even AlphaGo Zero approach would be not enough even for small boards like 7x7 to approximate the optimal komi value.


What would we call this datastructure? Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since it has variable number of leaves and branches on each node. It isn't a forest, since it doesn't consist of a list of trees. I'm not exactly sure what to call it.

For context, the specific structure I'm designing is used as part of a compiler. The language is indentation structured, so blocks of code are grouped by their indentation level.

I have an Indentation_______, which is a list of nodes where the node is either a statement in the program, or a new Indentation_______ containing the next nested indentation level.

Any ideas?

A tree is not restricted to a certain branching factor. A n-ary tree may only have a branching factor of n (or less), but in an unrestricted tree, each node may contain an arbitrary number of subnodes.

A tree is a connected graph without cycles, so your datastructure still satisfies that definition.

Alternatively you could call your structure something like "nested lists".


Organizing a "speedback" Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people.

I'm in a team and I want to plan the ideal speedback setup: all team members have to give feedback to eachother.
I want to group people in a way that maximizes the concurrency of simultaneous pairs so we reduce the total time of the sessions.

Consider the input:
"alexandre", "sergiu", "joana", "tiago", "susana", "david"

combinations(6,2) = 15 possible pairs

1st session:

"alexandre" with "sergiu"
"joana" with "tiago"
"susana" with "david"

2nd session:

"alexandre" with "joana"
"sergiu" with "tiago"
"joana" with "david"

3rd session:

...

you get the ideia.. until everyone "dates" everyone.

I need all the possible pairs to be matched in the end.

Do you how to get this output? (or can you hint about the solution)?

Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$.

Case 1: $n$ is even. In this case, $K_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ edges. Hence we can hope for a partition of $K_n$ into $n-1$ perfect matchings. This is a standard problem, known as 1-factorization of the complete graph. Here is one solution:
$$
(0,n-1),(1,n-2),(2,n-3),(3,n-4),\ldots,(n/2-1,n/2) \\
(1,n-1),(2,0),(3,n-2),(4,n-3),\ldots,(n/2,n/2+1) \\
(2,n-1),(3,1),(4,0),(5,n-2),\ldots,(n/2+1,n/2+2) \\
\ldots
$$
Explanation: the $i$'th row consists of $(i,n-1)$ together with $(j+i,n-1-j+i \bmod n-1)$ for $1 \leq j \leq n/2-1$. For example, when $n = 6$ you get:
$$
(0,5),(1,4),(2,3) \\
(1,5),(2,0),(3,4) \\
(2,5),(3,1),(4,0) \\
(3,5),(4,2),(0,1) \\
(4,5),(0,3),(1,2)
$$

Case 2: $n$ is odd. In this case, $K_n$ still contains $\binom{n}{2}$ edges, but now each matching contains at most $(n-1)/2$ edges. Hence we can hope for a partition of $K_n$ into $n$ almost-perfect matchings. We can take the solution above for $n+1$, and just ignore the match of vertex $n$. This gives the following solution:
$$
(1,n-1),(2,n-2),(3,n-3),\ldots,((n-1)/2,(n+1)/2) \\
(2,0),(3,n-1),(4,n-2),\ldots,((n+1)/2,(n+3)/2) \\
(3,1),(4,0),(5,n-1),\ldots,((n+3)/2,(n+5)/2) \\
\ldots
$$
Explanation: the $i$th row consists of $(j+i,n-j+i \bmod n)$ for $1 \leq j \leq (n-1)/2$. For example, when $n = 7$ you get:
$$
(1,6),(2,5),(3,4) \\
(2,0),(3,6),(4,5) \\
(3,1),(4,0),(5,6) \\
(4,2),(5,1),(6,0) \\
(5,3),(6,2),(0,1) \\
(6,4),(0,3),(1,2) \\
(0,5),(1,4),(2,3)
$$


Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable $$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$

I have to prove that this is not R.E. and not co-R.E.

I know how to approach these kind of problems. For
$\check L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| \le 1\)} \}$,
Here a simple reduction from complement of HP would do the trick. (Make a TM $M'$ which on input $w$ runs $M$ on $x$ and accepts if $M$ accepts $x$. If $\langle M,x \rangle$ belongs to complement of HP then $x$ would not be accepted and hence $M'$ would reject everything thereby satisfying the $\le 1$ property. Also in case $\langle M,x \rangle$ doesn't belong to complement of HP, $M'$ would accept everything and hence would be $\gt 1$. Thus we know that the complement of HP is reducible to $\check L$. Hence $\check L$ is not RE.)

But in the main problem I don't have an inequality and I am stuck with how to approach such problems. I would face the same problem while proving $L'$ (complement of $L$) as not RE for proving $L$ as not co RE.

One way to solve this problem is by showing there do not exist Turing machines that accept  $L_3$ or $\overline L$. But probably that is simply restating the question.

$L_u$, the universal language, is non-recursive but RE language. If we reduce $L_u \leq_M L$ then $L$ cannot be co-RE. If we reduce $L_u \leq_M \overline{L}$ then $L$ cannot be RE.

Let us  first do the reduction $L_u \leq_M L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows:
$M'$ rejects all inputs other than $w$. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M' = f(\langle M,w\rangle) \in L$.

Hence $L_u \leq_M L$. Therefore $L$ cannot be co-RE. Otherwise $L_u$ will become recursive.

Next we do the reduction $L_u \leq_M \overline L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M''$ as follows: Let $w'$ be a string other than $w$.
$M''$ rejects all inputs other than $w$ and $w'$. If the input in $w'$ then $M''$ accepts the input. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M''= f(\langle M,w\rangle) \not\in L$, that is, $\langle M,w\rangle \in L_u$ iff $M'' \in \overline L$.

Hence $L_u \leq_M \overline{L}$. Therefore $L$ cannot be RE. Otherwise $L_u$ will become recursive.

If we combine the results, $L$ is neither RE nor co-RE.


Prove that there always exists a line bisecting each of two point sets A line $\ell$ for a set $S$ of points is bisecting if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points.

Now given point sets $A$ and $B$ in the plane, prove that we can always find a line $\ell$ such that $\ell$ bisects both $A$ and $B$ simultaneously. We can assume that no three points in $A \cup B$ lie on a line and no two points share an x-coordinate.

Note that I am not asking for an algorithm separating $A$ and $B$.

So far I have proven the following claim:

  Let $S$ be a point set in the plane containing an even number of points. Prove that, for any point $s \in S$, a bisecting line $\ell$ for $S \setminus \{s\}$ also bisects $S$.

From this claim we can also infer that all separting lines for a point set $P$ with an odd number of points must pass through at least one point $p \in P$. However I am stuck on how to continue. Intuition suggests that one of the lines between points $a \in A$ and $b \in B$ must be simultaneously bisecting (if either of $A$ or $B$ contain an even number of points we can just remove one at random by the above claim). However I cannot seem to prove this is always the case.

Can you give me a hint for the next step?

We can prove this using the geometric dual of $P$ and $Q$.

Take the line arrangement of $P^*$ and $Q^*$ in the plane and let us look at the median levels $\Lambda_p$ and $\Lambda_q$. Their intersection is definitely a possible solution because $\Lambda_p$ is the point set describing the dual of all bisecting lines for $P$, and vice-versa for $Q$.

Note the following: Since $|P|$ and $|Q|$ are odd, both median line arrangements have the same slope (and since all slopes are unique by assumption, they must correspond to the same lines) in the beginning and the end of the arrangement. Let us denote $p^*$ and $q^*$ as the respective lines. Then at the beginning (i.e. the largest x-value where no intersections occured yet), one must be above the other and at the end (i.e. the smallest x-value such that no intersections happen from now on forward), they must have switched places.

Since the levels $\Lambda_p$ and $\Lambda_q$ are piecewise continuous (actually even continuously extensible), by the intermediate value theorem they must intersect in at least one point $c^*$, which is the dual of a possible simultaneously bisecting line $c$.


Can PDA have empty stack transition? From a youtube video, this PDA can recognize any palindrom.

However, from wikipedia, here is one of the criteria of PDAs.
We clearly see that the transition function can't take an empty stack as input, as epsilon is not a part of Gamma. (but it can use it as output, and also epsilon input is allowed as we see in the union).
But in the video, all transitions from q2 use empty stack as input stack character. What's wrong ?

1- The PDAs in the video seem to have a transition function of the form $\delta: Q\times (\Sigma\cup\{\epsilon\}) \times (\Gamma \cup \{ \epsilon\}) \to 2^{Q\times (\Gamma \cup \{\epsilon\})}$, so you are allowed to take a nondeterministic transition without reading any input letter and without popping a letter from the stack. Note however, that you are allowed to push a single letter (or none) to the stack in a transition that you take.
2- The PDAs from Wikipedia do not allow you to take a transition without popping a letter from the stack (note that as Yuval said:  the stack is initialized with a "bottom of stack" symbol), however note that, unlike the PDAs in item 1, you can push an entire word in the stack in a transition that you take.
So you have two variants of PDAs that have slightly different syntax, however it is not hard to prove that a PDA from one variant can simulate a run of a PDA from the other variant, and thus both variants recognise the same class of languages, CFL. A high-level explanation of how both variants can simulate each other is given next. A PDA $A$ of the 1st variant simulates a run of a PDA B of the 2nd variant by first pushing a "buttom of stack letter", then $A$ mimics the transitions that $B$ takes: in the case where $B$ takes a transition that pushes a word of length $\geq 2$ into the stack, you can introduce new states that push that word, and then move to the state that $B$ moves to. Conversely, a PDA $B$ of the 2nd variant simulates a run of a PDA $A$ of the 1st variant by first popping the "buttom of stack letter", then $B$ mimics the transitions that $A$ takes: the non-trivial part here is to mimic popping $\epsilon$ from the stack. This is easy as $B$ is allowed to push an entire word into the stack: popping $\epsilon$, and then pushing a word $w$, is equivalent to popping a letter $\sigma$, and then pushing the word $\sigma\cdot w$.


examples for: A is mapping reducible to B but B is not mapping reducible to A I find it hard to find reductions that only work on one side:
A is mapping reducible to B, but B is not mapping reducible to A.
what could be an easy way to find such two languages A,B ?
I tried Atm,Htm,EQtm,Etm,RegTm, and many others, and whenever I found that A is reducable to B, I also found that B is reducable to A.

thanks.

I now understand that there is a mapping reduction from the empty language to any other language except Sigma*, and there cannot be a reduction from a language to the empty language except for a reduction from the empty language to the empty language.


How would P2P Kriegspiel be designed? Kriegspiel chess is a variant of chess in which each player is not aware of where the opponent's pieces are. In a human match, a trusted intermediary relays piece losses, legality of moves etc. This is, of course possible on a computer as well. What would a peer to peer implementation of Kriegspiel look like, in terms of algorithms for authentication, one in which:

There is nobody sending or receiving information besides the two players.
Each player can independently verify the information sent is true (storing previous data is of course allowed)
All the functions of the intermediary are filled (players are aware of invalid moves, and of when pieces are taken.
No player is sent information which makes him certain of information he shouldn't know (e.g the position of the opponent's pieces) besides logical means, of course.

I have looked into zero knowledge proofs somewhat, and was interested in a way they could be implemented in a situation like this.

How would a cheat-proof version of P2P Kriegspiel be implemented?

or, alternatively since that question was deemed too vague

What computer science concepts, protocols, and general algorithms would go into the implementation of such a game?

It would use secure 2-party computation. There would probably be commitments to the statuses of the pieces and oblivious transfers to simulate referee responses and zero-knowledge protocols to show that the players are behaving as they should with respect to the above 2 parts.

If you're taking the oblivious transfer functionality as given and assuming the players are semi-honest, then I'm willing to try coming up with more details here.  On the other hand, if you're interested in how the oblivious transfers would be performed or how the zero-knowledge protocols would work, then you should ask on crypto.


How to create a cellular automata rule to achieve a desired pattern? Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is exhaustive and computationaly intensive.

Is there a way to derive the rule that would generate the desired pattern?

One way to achieve what you describe would be to encode your problem as a SAT instance, with clauses decribing the desired initial and final pattern and the state transitions under the (fully or partly unknown) evolution rule, and then let a generic SAT solver look for a solution.

In fact, at least for certain classes of rules (specifically, two-state isotropic rules on the Moore neighborhood, a class that includes e.g. Conway's Game of Life), you won't even need to implement this yourself, since there is an existing program called LLS that can do exactly that.  While a full tutorial on how to use LLS is beyond the scope of this answer, one of the things it can do is take a partial rule string (i.e. a description of the state transition rule, with some transitions left unspecified) and a list of grids fully or partially describing the evolution of a pattern over several generations, and search for a solution that fills in the unspecified bits of the transition rule and/or the pattern.


If P = NP, would dynamic programming be obsolete? I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic programming would have a more efficient (polynomial) way to solve? Or are there problems that even if P = NP, we would still use dynamic programming

Absolutely not. P = NP doesn't imply that problems that can be solved with dynamic programming can be solved easier or quicker with another algorithm.


Determining which recursive term is bigger if they share the same definition We are given a recursive definition:
$a_1 = x,\\a_2=y,
\\a_n= c_1a_{n-1}+c_2a_{n-2}  \text{ for }n\ge3 $
where $x,y,c_1,c_2,n$ are natural numbers
we are to prove that $a_n \le c_3^n$ for all n
The base case is true
Assuming $a_k \le c_3^k$ is true
show $a_{k+1} \le c_3^{k+1}$ is true

We have:

$c_3a_k \le c_3^{k+1}$

and

$a_{k+1} = c_1a_k + c_2a_{k-1}$

where 1 can be written:

$c_1a_k + ma_k$

where $m+c_1 = c_3$
which can be rewritten:

$c_1a_k + mc_1a_k + mc_2a_{k-1}$

Now, 4 and 2 have the first term equal.
How can I determine whether $ mc_1a_k + mc_2a_{k-1}$ in 4  is bigger or not than $ c_2a_{k-1}$ in 2?

Let $c_3 = \max(1,x,y,c_1+c_2)$. Then
$$
a_1 = x \stackrel{c_3 \geq x}\leq c_3^1
$$
and
$$
a_2 = y \stackrel{c_3 \geq y}\leq c_3 \stackrel{c_3 \geq 1}\leq c_3^2.
$$
Now suppose that $a_{n-2} \leq c_3^{n-2}$ and $a_{n-1} \leq c_3^{n-1}$. Then
$$
a_n = c_1 a_{n-1} + c_2 a_{n-2} \stackrel{\text{assumption}}\leq c_1 c_3^{n-1} + c_2 c_3^{n-2} \stackrel{c_3 \geq 1}\leq c_1 c_3^{n-1} + c_2 c_3^{n-1} \stackrel{c_3 \geq c_1+c_2}\leq c_3^n.
$$


Faster computation of $ke^{-(x - h)^2}$ The question is quite simple; almost every computer language today provides the $\exp(x)$ function in their standard library to compute expressions like $ke^{-(x - h)^2}.$ However, I would like to know whether this function is the fastest way to compute the above expression. In other words, is there some way to compute $ke^{-(x - h)^2}$ faster than $\exp(x)$ in standard libraries while keeping the result very accurate?
I would like to specify that Taylor series will not work for my application, nor will any other polynomial approximations.
In the end, I wish to compute a series of these expressions, $$\sum^n_{i = 0} k_ie^{-(x - h_i)^2}$$ for some integral $n \geq 0.$

There are several reasons why your standard library implementation of exp is slower than you might hope:

It should to be accurate to 0.5ulp (or 1ulp at worst), no matter what number you give it. This means that special care may need to be taken, say, in the subnormal range.
It needs to work for all floating point numbers, and return a reasonable answer for all of them. Assuming that you're on an IEEE-754 platform, this includes NaN, Inf, etc. The standard explains what the "correct" answer is for all of those cases, and the library function needs to get it right.
It may not be specialised for your specific instruction set (i.e. your CPU may have some advanced floating-point instructions that libc doesn't use by default).

This is what it means to be general-purpose.
Chances are that your standard library has had a lot of effort put into it, and you cannot beat it and still be general-purpose. To get more performance, you need to relax some restrictions. So we're going to need some details. How much accuracy is enough? Can you assume anything about the range of inputs?
I've gone through a typical implementation elsewhere (see this previous answer), and that should help you get an idea of how these things can be implemented.


An elementary oracle query Why is $P^{NP}\not\subseteq NP$ possible? After all we have a $P$ machine which uses an $NP$ oracle and since $P\subseteq NP$ why cannot the $P$ machine with $NP$ oracle just be replaced by an $NP$ machine?

Similarly why is not the case $P^{coNP}\subseteq coNP$?

A $\mathsf{P^{NP}}$ machine can solve $\mathsf{coNP}$ problems: it can query an $\mathsf{NP}$ oracle, and then return the opposite answer. This is not something that you can obviously simulate with an $\mathsf{NP}$ machine.

More concretely, you can construct $\mathsf{P^{NP}}$ machine which gets a formula as input, accepts if the formula is unsatisfiable, and rejects if the formula is satisfiable. How would you implement this as an $\mathsf{NP}$ machine? We only know how to construct witnesses for satisfiability (namely: a truth assignment), but not for unsatisfiability.


what are read/write operations involved in main memory, cache and processor? please bear with me, I always get confused with the terminologies used in my computer architecture class.

What are read and write operations exactly? What are their relationship with processor, main memory, and cache?

I always thought that load/store are interchangeable with read/write...

What about the modify operation?

Read is the same as load, and write is the same as store. Modify is a combination of both.


Why 2 way DFA have the same power as one way DFA? I was looking through some papers online on the equivalence of 2-way DFA and 1-way DFA and I couldn't find a simpler explanation on why 2DFAs are no more powerful than ordinary DFA. I wanted to write a simpler explanation of why this is the case so anyone who is new to the topic could understand without much trouble.

It would be helpful if someone could point me to some resources on the topic that are simple to understand

The intuitive explanation why two-way DFA and NFA are not more powerful than DFA is that all these variations have finite memory. A non-deterministic or two-way automaton has more memory per state than a basic DFA, but as long as there's only a finite amount of memory, a fancy automaton is no more powerful than a DFA with perhaps more states.

A two-way DFA can retrace its steps, but it has no memory of it. When the automaton is at a certain position in the input, the only thing that encodes how it got there is the state, and it's taken from a finite state. So there's no way for the automaton to behave differently based on the position or the movement history.

Let's look a bit more precisely at how a DFA can simulate a two-way DFA, i.e. how the memory of a two-way DFA can be represented in a DFA. The states of a DFA represent all that is known about the input after reading a prefix of the input. Reading a word $uv$ can be decomposed into 1. reading $u$ from the initial state and 2. reading $v$ from the state reached after reading $u$. The information about the partial input $u$ that the DFA remembers is simply the state reached after reading $u$.

Before studying this for a 2DFA, let's do it for an NFA. An NFA reads its input sequentially from left to right like a DFA, but at each stage, any set of states of the NFA may potentially be reached. Thus, the information about a partial input that the NFA remembers is the set of reached states. There are at most $2^n$ sets of states in a world with $n$ states, and therefore an NFA with $n$ states can be simulated by a DFA with at most $2^n$ states. This is in fact a tight bound.

In an NFA with $n$ states, the amount of information in the system is encoded in the set of reachable states. Each new input character triggers a transition from a set of states to a new set of states. Since there are $2^n$ sets of states, an NFA can be converted to a DFA that recognizes the same language and that has at most $2^n$ states.

Let's now turn to a two-way DFA with $n$ states. After reading some input $u$, the 2DFA remembers what state it has reached. In addition, after reading more input, the 2DFA may backtrack into $u$ and, perhaps, come back out. We want to abstract $u$ away completely, so we need to count all the ways to backtrack into $u$ and come back. If the 2DFA ever backtracks into $u$, it may do so from any state $q$ amongst its $n$ states. When it comes back out, it will have reached some other state $q'$ (perhaps the same, it doesn't matter). The state $q'$ depends on $q$ and $u$, but it doesn't depend on what comes after $u$, since by definition $q'$ is the state reached after working through $u$ in a deterministic automaton. Therefore each prefix $u$ defines a mapping from $q$ to $q'$. The information stored in the 2DFA after processing $u$ consists of the initial exit state (which state is reached immediately after reaching the end of $u$) and the mapping from reentry state to subsequent exit state. (I don't claim that all mappings are possible.) There are $n$ initial exit states, and $n^n$ mappings of state to state. Thus the information in a 2DFA after processing some prefix consists of at most $n \times n^n$ different possibilities. This means that a 2DFA can be simulated by a DFA with at most $n \times n^n = n^{n+1}$ states.

The tight bound is in fact $n \times (n^n - (n-1)^n)$. I don't have an intuition for the second term.


What is the decision version of integer programming? I don't know what is meant by "decision version of integer programming".

I know ILP, but this terminology has me confused.

It's the same was for all NP problems; the optimisation problem is

  Find a valid solution $s$ that minimises¹ $f(s)$!

and the corresponding decision problem is

  Is there a valid solution $s$ with $f(s) \leq k$?

You see that the former immediately solves the latter, and you can solve the former by using the latter with binary search over the set of feasible $k$.

Of course, you can have "maximise" here and "$\geq k$" in the decision version.


Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$? I was trying to find a cf-grammar for $L = \{a^{2^n}| n \geq 1\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?

It's a more or less standard result that the language in question isn't  context-free, so the answer to your question is no. The same holds for a number of similar languages, like
$$
L_1= \{a^{n^2} \mid n\ge 0\}\quad\text{and}\quad L_2=\{a^p\mid p\text{ is prime}\}
$$
There's a nice property that can be useful in cases like this: any context-free language over a one-symbol alphabet is regular. This, combined with a characterization of regular languages over a unary alphabet implies that languages like the ones above cannot be context-free since they're too "sparse".


Efficient way to calculate the maximum curvature of a cubic spline I've got a 2D cubic spline (Bézier) and I have the polygon-line that's a discretization of that spline.

Is there an efficient and simple to implement a way to calculate the maximum curvature of the spline either by using its smooth representation or the discrete poly-line? It doesn't have to be exact since it's for a game, an error around 10% would be totally acceptable.

Different wording: I would like to know: if I'd drive a car driving at constant speed along the spline, what would be the maximum degree I had to turn the steering wheel to stay on it?

Step 1: Express the points on the spline parametrically, so the spline is the set of points of the form $(x(t),y(t))$, where $t$ is a parameter.  Here $x(t)$ represents the $x$-coordinate (as a function of the parameter $t$) and $y(t)$ represents the $y$-coordinate.  Since this is a cubic spline, you can find functions $x(t),y(t)$ that are cubic polynomials with known coefficients that provide this parametric expression.

Step 2: Use the formula on Wikipedia for computing the curvature, given a parametric representation of the curve.  This gives you a formula for the curvature as a function of $t$, namely, $\kappa(t)$.  Note that since $x(t)$ and $y(t)$ are cubic polynomials, you can explicitly compute their first and second derivatives, so you can analytically compute an explicit expression for $\kappa(t)$, i.e., for the curvature as a function of $t$.

Step 3: Find the value of $t$ that maximizes $\kappa(t)$.  Note that we are now dealing with a function $\kappa : \mathbb{R} \to \mathbb{R}$, i.e., we are in the one-dimensional case. Thus, we can find the maximum numerically using any of a number of methods: gradient descent, Newton's method, or a number of other methods.

Alternatively, you can analytically compute the derivative of $\kappa(t)$, and then solve the equation $\kappa'(t)=0$ for $t$.  This might allow an analytic solution that identifies a list of candidate maxima of $\kappa(t)$.  Make sure to also check the endpoints (the lower and upper bounds for $t$).  Evaluate $\kappa$ at each candidate and pick the one that makes the value of $\kappa(t)$ as large as possible.


Semantics of E and A operators in CTL* I'm referring to a book where E and A were defined in text as follows

  The formula $A \phi$ states that all the executions out of the current state satisfy property $\phi$ whereas $E\phi$ states that from the current state, there exists and execution satisfying $\phi$

And formally, they were defined as

  $\sigma, i \models E\phi $ iff there exists as $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ and $\sigma', i \models phi$
  $\sigma, i \models A\phi $ iff for all $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$, we have $\sigma', i \models phi$

$\sigma(i)$ was previously defined to be the ith state of an execution $\sigma$.

Here's where my confusion lies. Doesn't $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ imply that the executions $\sigma$ and $\sigma'$ have both the same start and end state, therefore $\sigma', i \models \phi$ is same as $\sigma, i \models \phi$? That seems to be wrong.

I believe it means that $\sigma,\sigma$ should share the same prefix up to position $i$.
Then the quantification ranges over all possible extensions of this prefix from state $\sigma(i) = \sigma(i)'$.


Term for a graph decomposition based on a maximum matching Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:

$Y_1 = $ the neighbors of $X_0$ using edges in $E\setminus M$.
$X_1 = $ the neighbors of $Y_1$ using edges in $M$.
$Y_2 = $ the new neighbors of $X_1$ ("new" = not in $Y_1$) using edges in $E\setminus M$.
etc...

Since the graph is finite, at some point we stop finding new vertices, so the process stops and we have a maximal sequence.

Let $X_S,Y_S$ be the vertices contained in the sequence, and $X_L,Y_L$ the leftover vertices:

We have a decomposition of $X$ and $Y$ into two subsets.
This decompositionhas some nice properties (for example, $X_L$ and $X_S$ are the same regardless of what maximum matching $M$ we start from).

Such a nice decomposition must have a name... what is its name? And what is a standard reference for the decomposition and its properties?

Looking at the image in the question, I get the impression that $X_L\cup Y_S$ is a minimal vertex cover of the graph $G$. (This is not fully true: If $X$ contains isolated vertices, then those would be part of $X_L$, but not of a minimal vertex cover.) Good, but there can be many vertex covers of a graph, so this does not yet fully characterize that specific decomposition. So let us look at the construction in more detail: Any minimal vertex cover must contain at least one vertex from every matched edge. Since the vertices in $X_0$ don't belong to any matched edge, covering the edges incident to $X_0$ by vertices (from $Y$) belonging to matched edges is the best we can do. So $Y_S$ turns out to be the biggest subset of $Y$ belonging to every mimimal vertex cover of $G$. (So it is the intersection of the $Y$ part of all minimal vertex covers). And $X_L$ is the unique subset of $X$ covering the remaining edges (+ the isolated vertices of $X$).

OK, so how is this related to the Dulmage-Mendelsohn decomposition? (set $U=X$ and $V=Y$).

  ..., let $D$ be the set of vertices in $G$ that are not matched in at least one maximum matching

I guess the neighbors of $D\cap X$ belong to any minimal vertex cover, and the neighbors of $D\cap Y$ also belong to any minimal vertex cover. So $Y_S$ is also part of (or at least easily defined) for the Dulmage-Mendelsohn decomposition. Can we also define $X_L$ in terms of the Dulmage-Mendelsohn decomposition? Well, it is easier to define $X_S$, it should be just $D\cap X$.

This all sounds much more complicated than it actually is. If you look at the possible alternating paths for the given maximum matching, it should be easy to see the relation between the minimal vertex cover and the set $D$ used to define the Dulmage-Mendelsohn decomposition.


Algorithm Design for Linear Programming I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.

I am working on the following problem:

  Suppose you are consulting for a company that manufactures PC. equipment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply $s_i$ of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each weeks supply can be carried by one of two air freight companies, $A$ or $B$.

  Company $A$ charges a fixed rate $r$ per pound (so it costs $r$ x $s$ to ship a week's supply $s_i$).
  Company $B$ makes contracts for a fixed amount $c$ per week. independent of the weight. However, contracts with company $B$ must be made in blocks of four consecutive weeks at a time.

  A schedule for the PC company is a choice of air freight company ($A$ or $B$) for each of the $n$ weeks with the restriction that company $B$, whenever it is chosen, must be chosen for blocks of four contiguous weeks in time. The cost of the schedule is the total amount paid to company $A$ and $B$, according to the description above.

  Give a polynomial-time algorithm that takes a sequence of supply values $s_1, s_2, \cdots, s_n$ and returns a schedule of minimum cost. For example, suppose $r = 1$, $c = 10$, and the sequence of values is
  $11, 9, 9, 12, 12, 12, 12, 9, 9, 11.$

  Then the optimal schedule would be to choose company $A$ for the first three weeks, company $B$ for the next block of four contiguous weeks. and then company $A$ for the final three weeks.

I am trying to write algorithm, in pseudo code, that completed the following steps in order to solve the challenge, but I don't know even where begin this solution. My initial suspect on how to solve this:

Determine what the "optimal" formula looks like, which is: MIN((r*s + OPT(i-1), (3c + OPT(i-3))

This would determine the most optimal between $A$ or $B$ given their restrictions.
Therefore I would need to determine the most optimal schedules for the weeks preceding the $i^{\text{th}}$ week. Meaning I would end up running OPT(n-1) for every n, thus resulting in OPT(n) total runs so (n) time complexity.

Any advice on how to generate pseudocode for this would be appreciated...I am trying to learn but am not very effective.

The approach you used is called dynamic programming.

In dynamic programming, a series of decisions are made in order to maximize some function, where the options available at any given time depend on the decision we have made before. You may want to check a tutorial on TopCoder or some course material at your hand.

You have started to figure out the recurrence relation, the hallmark of dynamic programming. However, it looks like you made an off-by-one error.

You can imitate the pseudocode in that tutorial. Or many other pseudocode such as those in the Introduction to algorithm by Corman et al.

Here is my pseudocode for this problem, where you can find the correct recurrence relation. I assume $n\ge4$; otherwise the only choice is to use
company $A$ always.

Let $OPT$ be an array of size $n$.
$OPT[0]=0$, $OPT[1]=s_1r$, $OPT[2]=(s_1+s_2)r$, $OPT[3]=(s_1+s_2+s_3)r$
For $i$ = 4 to $n$,  $OPT[i] = \min(OPT[i-1] + s_ir, OPT[i-4] + 4c)$
Output $OPT[n]$


Proof of Strong Duality Via Farkas Lemma I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:

Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$

Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$

Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.

The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.

Prove this using the following hint: If it is false, then there cannot be any solutions to

$$AX \ge b, \; A^tY \le c, \; X \ge 0,\; Y\ge 0, \; c^tX \le Y^tb.$$

My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.

Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.

Assume for contradiction that the hypothesis is wrong:

$$\begin{bmatrix}
A^t & -c\\
0 & -1
\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$

By Farkas' Lemma, we know the following system is solvable:

$$\begin{bmatrix} X & w_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w_2 \ge 0$.}$$

Now, from the system above, we may write $XA^t \ge b^t$, and
$Xc \le \lambda - w_2$.

If $w_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1.  However, one cannot reach that conclusion if $w_2$ is exactly $0$.

I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.

The following is based on the book "Combinatorial Optimization" by Papadimitriou and Steiglitz (chapter 3)

On LP duality, they first state a theorem that when a LP has a feasible solution, the dual also has one and on optimality their costs are equal (Theorem 3.1 in the book, based on the simplex algorithm)

This follows from the fact that the dual cost is always dominated by the primal cost.

i.e let $x$ and $\pi$ the solutions to the primal and dual respectively, then (i.e $c'$ is transpose vector of $c$)

$$c'x \ge \pi'Ax \ge \pi'b$$

So if the primal has a feasible solution so does the dual and on optimality they (the costs) are equal.

Then the Farkas Lemma (theorem 3.5 in the book) is proved based on this theorem.

But one can reverse the proof of Farkas Lemma in the book and prove Th. 3.1 from Farkas Lemma (Th. 3.5)

A sketch:

Farkas' Lemma states that (as stated in book):

  Given vectors $a_i \in R^n$, $i = 1,..m$ and another vector $c \in R^n$,

  iff $y'a_i \ge 0, \forall i \implies y'c \ge 0$, then $c \in C(a_i)$
  (i.e $c$ is in the cone generated by $a_i$)

Consider a LP:

$$\min{c'y}$$
$$a_i'y \ge 0, i =1..m$$
$$y \ne 0$$

The LP is feasible and bounded because $y = 0$ is a feasible point and $c'y \ge 0$ (by the lemma)

$c$ can be expressed as linear combination of the $a_i$'s using a vector $\pi$, where $\pi_i \ge 0$, i.e

$$c = \sum_1^m{\pi_i a_i}$$

Constructing the dual of the LP as:

$$A_j = col(a_{ij}, i=1..m) \in R^m$$
$$a_i = col(a_{ij}, j=1..n) \in R^n$$

gives the dual LP:

$$\max{0}$$
$$\pi'A_j = c_j, j = 1..n$$
$$\pi \ge 0$$

which has a feasible solution ($\pi$) and equal cost at optimality (strong duality theorem)


The number of Binary Search Tree that exist with same Postorder and Inorder how many BST exist with same postorder and inorder traversal?

I know that in binary tree (Not BST), it is one.

but i have a book from that said for BST it is CATALAN number. i become confused.

Your confusion might stem from this: The number of binary trees on $n$ vertices is $C_n$, the $n$-th Catalan number. Since in a BST, the left-right order of vertices is fixed, the number of BSTs with a given inorder traversal is also $C_n$. However, with the added restriction that the postorder traversal must be the same as the inorder traversal, the BST can only have left branches.

In more detail, recall that inorder = left-visit-right and postorder = left-right-visit.

If both traversals must be the same (visit is at the root) there can be no right subtree, and this is then the same at the left child, and so on. This leaves only one form: a tree with only children to the left.

What is your book stating, more precisely? Perhaps we can find the reason for the confusion.


NFA automata with $\epsilon$ moves I'm trying to understand the NFA and $\epsilon$ moves logic.
Let's say there is an NFA $A$ with $\epsilon$ moves,
if $\epsilon ∈ L(A)$ then $q_0 \in F$? and vice versa? If $\epsilon \in L(A)$ then $q_0 \in F$?
How can I prove it?

It is true that if $q_0 \in F$ then $\epsilon \in L(A)$. The converse holds for DFAs and for NFAs without $\epsilon$ moves, but doesn't hold for NFAs which are allowed to have $\epsilon$ moves. That is, there is an automaton $A$ whose initial state is not accepting, yet $\epsilon \in L(A)$. I'll let you find an example.


Expected number of iterations for bozo sort opt algorithm I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2:
http://www.hermann-gruber.com/pdf/fun07-final.html

I know the maximum number of inversions in this case is nC2, what i'm struguling with is the probability of two numbers in an iteration being an inversion.

Here is the relevant piece of the paper I'm focusing on, I know the answer to the number of iterations is there, I just can't seem to get to it.

  3.2 Comments on optimized variants of bogo-sort

  Though optimizing the running time seems somewhat out of place in the field of pessimal algorithm design, it can be quite revealing for beginners in both fields of optimal and pessimal algorithm design to see how a single optimization step can yield a dramatic speed-up. The very first obvious optimization step in all aforementioned algorithms is to swap two elements only if this makes sense. That is, before swapping a pair, we check if it is an inversion: A pair of positions $(i, j)$ in the array $a[1, \dots, n]$ is an inversion if $i < j$ and $a[i] > a[j]$. This leads to optimized variants of bogo-sort and its variations, which we refer to as bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$, resp. As there can be at most $\binom{n}{2}$ inversions, this number gives an immediate upper bound on the number of swaps for these variants—compare, e.g., to $\mathcal \Omega(n*n!)$ swaps carried out by bogo-sort. It is not much harder to give a similar upper bound on the expected number of iterations. As the number of comparisons during a single iteration is in $\mathcal O(n)$, we also obtain an upper bound on the expected total number of comparisons:

  Lemma 14. The expected number of iterations (resp. comparisons) carried out by the algorithms bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$ on a worst-case input $\overline x$ of length $n$ is at most $\mathcal O(n^2\log n)$ (resp. $\mathcal O(n^3\log n)$).

The bounds in that paper can be tightened. The tighter bounds in lemma 14 are "..." at most $O(n\log n)$ (resp. $O(n^2\log n))$.

As in the question and the papers, we will fix a set of $n$ elements that are totally ordered. The array $a=(a_1, a_2, \cdots, a_n)$ will be a permutation of the $n$ elements. A pair of element $\{a_i, a_j\}$ is a good pair if $i\lt j$ and $a[i]\lt a[j]$. It is a bad pair if $i\lt j$ and $a[i]\gt a[j]$. A bad pair is also call an inversion.
Fact on inversion. Swapping a bad pair strictly decreases the number of all inversions. An array is sorted if and only if the number of all inversions is 0. The maximum number of all inversions is the same as the numbers of all pairs, $\binom n2$.
Now we will use the fact above to show the tightened version of lemma 14 for one case.
The expected number of comparisons carried out by bozo-sort$_{\text{opt}}$ on a worst-case input $x$ of length $n$ is at most $4n^2\log n + (n-1)$, where $\log$ is the natural logarithm.

Proof: Suppose there are $m$ bad pairs in the array. A run of procedure rand. transpose hit one with probability $p = m/n^2$, so the expected number of runs of that procedure until we hit a bad pair is $1/p=n^2/m$. Since the number of bad pairs decreases each time we swap a bad pair, the expected number of runs of  that procedure until the array is sorted is bounded by
$$\sum_{m=1}^{\binom n2}\frac{n^2}m=n^2\sum_{m=1}^{\binom n2}\frac1m\le 2n^2\log n$$
Note that each procedure rand. transpose makes one comparison. The effect of running procedure sorted before every $n-1$ procedure rand. transpose will at most double number of comparisons besides the initial $n-1$ comparisons. Q.E.D.
The above proof is adapted from Fun sort or the chaos of unordered binary search by T. Biedl, T. Chan, E. D. Demaine, R. Fleischer, M. Golin, J.A. King, and J. I. Munro. Discrete Applied Mathematics, 144(3):231–236, 2004.
Exercises
Exercise 1. Show that $\sum_{m=1}^{\binom n2}\frac1m\le 2\log n.$ (Hint, here is the rate of divergence of harmonic series).
Exercise 2. (One minute or less.) Show that ${m}/\binom n2$ is the probability of procedure rand. transpose in bozo-sort$^+_{\text{opt}}$ hitting one bad pair when there are $m$ bad pairs.
Exercise 3. Show that the expected number of bad pairs found (and, swapped) by a call to procedure randomly permute in bogo-sort$_{\text{opt}}$ when there are $m$ bad pairs is $\Theta(m(n-1)/n^2)$. Show the expected number of total comparisons until the array is sorted is at most by $\Theta(n^2\log n)$.


Graph of size n with girth >2k and minimum degree more than n^1/k I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$.
The proof is made by contradiction where repeatedly any node from $G$ of degree at most $\lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $G'$ of $G$ of minimum degree more than $\lceil n^\frac{1}{k}\rceil$.
The conclusion is that $G'$ must have girth at most $2k$ and therefore also $G$, which is a contradiction.
I don't understand the conclusion: Why must $G'$ have girth at most $2k$? Why is it not possible that $G$ has girth more than $2k$ and minimum degree more than $\lceil n^\frac{1}{k}\rceil$?

I don't really see an answer to this question, so I would be very grateful if someone can help me.

Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N_1 > \lceil n^{1/k} \rceil$ neighbors. Each neighbor of $v$ has more than $\lceil n^{1/k} \rceil$ neighbors, and at least $\lceil n^{1/k} \rceil$ of them are different from $v$. The neighbors of different neighbors are all different, since otherwise $G'$ would have a 4-cycle. Denoting by $N_2$ the number of nodes at distance 2 from $v$, we have $N_2 \geq \lceil n^{1/k} \rceil N_1$. Continuing this way, we have $N_\ell \geq \lceil n^{1/k} \rceil N_{\ell-1}$ for all $\ell \leq k$ (here you use the lower bound on the girth; details left to you). In total, we get $N_k > \lceil n^{1/k} \rceil^k \geq n$, which is impossible.


BDD to CNF in linear time I have a book from my university that claims:

  There is an linear algorithm that can convert BDD to CNF in linear time, and generate CNF in linear length of the BDD size (number of nodes).

Then they wrote an exercise to find one...

Actually I tried to do so, I thought to find the paths that brings me to 0, and then translate them to clause (with the opposite value of the variables), and use Tseytin transformation to create linear length of CNF.

The problem are:

How can I find all the paths to 0? I thought about DFS but it seems to be complex task for DFS because I need the variables value (the naive algorithm is exponential)
The other problem is the variables to add, when should I create a new variable, every move? It can cause an exponential number of variables, which is not good.

So what is the correct algorithm to do that?

This is a nice exercise.  I'll give you a series of hints.  Click on each hint only after you've spent a good amount of time thinking on the previous one.  You'll get the most value by solving this on your own.

Hint #1:

   Add extra variables.

Hint #2:

   Use the Tseitin transform.  Review to convert CircuitSAT to SAT.

Hint #3:

   Introduce a boolean variable $x_v$ for each node $v$ in the BDD.

Hint #4:

   The idea is that $x_v$ should be true iff the path you follow goes through $x_v$.  Can you write clauses to ensure all of this?


Doubt on Graph on DFS The maximum number of edges possible in an undirected graph with 5 nodes, when DFS call made on any random node in the graph result stack size 5 i.e. 5 function call present in stack simultaneously are ____________________

How graph edges can be converted to a function call ? Is that mean here we have to do a recursive call. I am not getting clear, what is function call here. Plz help

Graph edges are not "converted to function calls". DFS is a recursive function. When you call DFS on some start node, it looks at the adjacent vertices (vertices which are connected to this node via an edge) and recursively calls itself on one of them.
But since each node is only visited once in a DFS, the maximum stack size cannot be greater than the number of nodes.


how can this function be computed in polynomial time in regards to its input? i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length)

defining a function from assignments of truth values to a set of booleans to 3CNF propositions:

the function gets an assignment of truth values to a set of n boolean variables $x_1,x_2,...,x_n$ (n ≥ 3) (meaning each boolean variables gets either 0 or 1).

the function returns a 3CNF proposition that upholds(maintains) the following:

1)each clause of the proposition contains exactly three literals

2)the proposition consists of only the variables $x_1,x_2,..,x_n$

3)the three literals in each clause are of different variables(there are no double literals in the clause, and none of the clauses consists of complimentary literals)

4)the proposition is satisfiable and the only assignment that satisfies the proposition is the assignment the function obtained as an input.

prove that the given function can be calculated in a polynomial time in regards to the input size

i don't understand how can it be computed in a polynomial time in regards to the input size. tried to look everywhere, this site, online, sipser's book and nothing. similar problems are usually from the NP family.

could someone please explain to me how this one can be polynomially computed? i just can't understand that

EDIT: this is how the final 3CNF should look in my opinion: $(l_1 \lor l_2 \lor x_1) \land  (\lnot x_1 \lor l_3 \lor x_2) \land (\lnot x_2 \lor l4 \lor x_3)\land ... \land(\lnot x_{n-3} \lor l_{n-1} \lor l_n)$ (from $(l_1 \lor l_2\lor...\lor l_n)$).

but what i don't understand is why is it polynomial, could someone please explain to me why can it be computed polynomially in regards to input size?

Let's start with solving the problem for 1-CNFs. The proof will be by example. If the truth assignment is $x_1=x_2=1,x_3=0$ then a 1-CNF for which this is the only satisfying assignment is
$$
x_1 \land x_2 \land \overline{x_3}.
$$
Now let's solve the problem for 2-CNFs, again by example. Continuing with our previous example, here is one possible construction:
$$
(x_1 \lor x_2) \land (x_1 \lor \overline{x_2}) \land
(x_2 \lor x_3) \land (x_2 \lor \overline{x_3}) \land
(\overline{x_3} \lor x_1) \land (\overline{x_3} \lor \overline{x_1}).
$$
More generally, we replace $x_i$ with $(x_i \lor x_j) \land (x_i \lor \overline{x_j})$ for an arbitrary $j \neq i$.

Your problem can be solved in a very similar way.


optimize string search on black-box function Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the constant? The strings should be lexicographical compared.

For example, given a handle to the following function, but not knowing the specific constant used:

fn lower_bound(s: &[u8]) -> bool {
    s >= &[10, 20, 30]
}

What is the optimal algorithm for determining the enclosed value of &[10, 20, 30]?  A maximum length for the value can be assumed if that makes it more tractable.

The most optimal algorithm would be to perform a binary search for each character sequentially (bin-search for 1st char, bin-search for 2nd char, ...etc).


Direct mapping cache with LRU I'm studying computer architecture and I'm doing an experiment.
Does LRU make sense in a direct mapping cache? I'm quite confused.
Thank you.

LRU only applies if the cache is set-associative and you need a hint as to in which set you write new data.  In a direct mapped cache, here is only one place to put data.


When to use Djikstra or Bellman-Kallaba algorithm? This the answer that was accepted for the arrangement problem of a library:

  we have books with heights $H_n,$ $1 \le n \le N$ and widths $W_n,$ with heights in ascending order for each book, and we want to group them into shelves.

  Reuse these numbers for solution nodes $n,$ where that node represents a solution state "all books $i \le n$ have been shelved." We will therefore start at node $0$ and seek to get to node $N$ by the shortest path with Dijkstra's algorithm. These nodes are the vertices of our graph.

  We then draw from node $i$ to any node $j \gt i$ a directed edge which assumes that all of those intermediary books will be shelved with one shelf, i.e. the length of this edge is $$L_{ij} = F_j + C_j~\sum_{n=i+1}^j W_n,$$where I have assumed that when you were saying the cost of the sum was $F_i + C_i x_i$ the subscript $i$ on the $x_i$ was totally meaningless.

  Dijkstra's algorithm will then give us a shortest-length path to node $N.$

With such an array, showing how many books do we have of length $H_i$ with $L_i$ meters of documents of $type \ i$, and the cost of storing such documents: $F_i$ a fixed command cost and $C_i$ the varying cost accorfing to $x_i$ the length of documents we would store within it,

\begin{array}{|c|rr}
i & 1 & 2 & 3 & 4\\
\hline
H_i & 12\,\mathrm{cm} & 15\,\mathrm{cm} & 18\,\mathrm{cm} & 23\,\mathrm{cm}\\
L_i & 100\,\mathrm{cm} & 300\,\mathrm{cm} & 200\,\mathrm{cm} & 300\,\mathrm{cm} \\
\hline
F_i & 1000€ & 1200€ & 1100€ & 1600€ \\
C_i & 5€/\mathrm{cm} & 6€/\mathrm{cm} & 7€/\mathrm{cm} & 9€/\mathrm{cm}\\
\end{array}

The graph is:

My question is: why should we use a Djikstra algorithm? We don't have any circuits and we can't go backward. Therefore, shouldn't we use Bellman-Kalaba algorithm?

Dijkstra's algorithm is faster (more efficient) than Bellman-Ford for graphs where it is applicable, i.e., for graphs where all edge weights are non-negative.  This is one such graph, as the cost of a bookshelf can never be negative.  Therefore, for this graph, Dijkstra's algorithm is better than Bellman-Ford.

(Incidentally, that answer is the accepted answer because you accepted that one.)


What do you call a lower/upper bound that is the best one? I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Is that right?

The phrase you're looking for is tight bound or in your case a tight upper bound.


Valgrind: what is the difference between a store and a modify? I am using the Vlagrind lackey tool to examine the full memory reference string of a running computer program and wonder what the difference between a "store" and a "modify" might be - and do these differences reflect a real difference in category of memory manipulation, or are they merely a convenience for the user/programmer of Valgrind's lackey tool?

The comments on the lk_main.c source code give these examples of (a) A store:

movl %eax, (%ebx)

And (b) a modify

incl (%ecx)

I appreciate this is a question about a specific piece of software, but what I really want to know is if it is valid to consider stores and modifies as, in effect "stores" - as much texts on memory seem to regard the two basic operations as load (read) and store (write).

This sounds like a question about the terminology that Valgrind happens to use, more so than a question about fundamental aspects of computer science.  I suggest you ask on a Valgrind support forum if you want an authoritative answer.

Based on your examples, it looks like the most likely answer is that the Valgrind folks are using the word "store" to mean "an operation that writes to memory, overwriting in a previous value with a new value that does not depend upon its previous value" while they mean "modify" to mean "an operation that writes to memory, updating its value to a new value that may depend upon the value previously stored in that location".  Only Valgrind folks can confirm authoritatively whether this is actually what they mean.


How to show that the set of TMs that accept languages of size two is recognizable? I know how to show $\overline{Lx}$ is unrecognizable.
I know how to show Lx is undecidable.

I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable.

For instance, to show $\overline{Lx}$ is unrecognizable, show $\overline{Htm}$ <= $\overline{Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
    def N(x):
        M('')
        if x == 0 or x == 1 then accept
    return <N>

  If M is in $\overline{Htm}$ then M loops then N will not accept any strings then
  |L(N)| = 0 then N is in $\overline{Lx}$

  if M is not in $\overline{Htm}$ then M halts then N
  will accept either 0 or 1 so |L(N)| = 2 then N is not in $\overline{Lx}$

I would like a similar proof to show that Lx is either recognizable or unrecognizable.

Based on RanG. answer in comments.

To show ${Lx}$ is unrecognizable, show $\overline{Htm}$ <= ${Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
    def N(x):
        if x == 0 or x == 1 then accept
        M('')
        return accept
    return <N>

  If M is in $\overline{Htm}$ then M loops then N will accept either 0 or 1 then
  |L(N)| = 2 then N is in ${Lx}$

  if M is not in $\overline{Htm}$ then M halts then N
  will accept all x so |L(N)| = $\infty$ then N is not in ${Lx}$


Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$? What I know is that $W = \lim V$ for some $V$ if and only if $W$ is the language of some deterministic buchi automata, namely that of $V$.

So, to attack this problem I tried to come up with some language of the form $U^\omega$ which cannot be determinized. But I keep failing trying to come up with something like this.

Is it true in general that given regular $U$, there is some regular $V$ such that $U^\omega$ = $\lim V$?

Consider the language $$U = U_1 \mid U_2 = a\Sigma^* \mid (\Sigma \setminus \{c\})^* b$$ for the alphabet $\Sigma = \{a,b,c,d\}$.

Let $\mathcal{A}$ be a deterministic Büchi automaton for the language $U^\omega$ with $n$ states. For every $n \in \mathbb{N}$, the word $w_1 = a(b^n c)^\omega$ should not be accepted, but the word $w_2 = a(b^n c)^m b^\omega$ should be accepted for every $m \in \mathbb{N}$.

The word $w_1$ should not be accepted because $U_1$ can only be used once (as there is only one $a$ in $w_1$), so in order for $w_1$ to be be accepted by $U^\omega$, a subword match with $U_2$ has to occur infinitely often -- but $U_2$ cannot accept subwords with a $c$.

The word $w_2$ should be accepted because $U_1$ accepts $a(b^n c)^*$, and $(U_2)^\omega$ accepts $b^\omega$.

Now by a pumping argument, we can see that from a prefix trace for a, when reading $b^n$, an accepting state in the Buchi automaton should be visited at least once, as otherwise we have a rejecting loop for the word $ab^\omega$. But then an accepting state is visited at least once for $ab^nc$. By an induction argument, we can then show that for every $m \in \mathbb{N}$, a trace for $a(b^nc)^m$ needs to visit accepting states at least $m$ times. Similarly, a trace for $a(b^nc)^\omega$ visits an accepting state infinitely often, even though this word is not in $U^\omega$. Hence, the assumption that $U^\omega$ can be represented as a deterministic Büchi automaton is false.


Haskell type class and initial algebra For the example below, I am trying to understand how Haskell type classes, type class instances, and data types relate to the concept of initial algebra.
There are two Haskell data types sharing a pair of operations for equality and addition. From my, perhaps incorrect, understanding the instances, which include the data types, specify two non-isomorphic initial algebras.
It seems to me that the type class permits the overloading of the operations and plays no role in the specification of the initial algebra.
Is this a correct interpretation of the given example?

data Nat0 = Zero | Succ0 Nat0 deriving Show
data Nat1 = One | Succ1 Nat1 deriving Show

class PeanoNum n where
 eq :: n -> n -> Bool
 add :: n -> n -> n

-- Two different non-isomorphic algebras.
instance PeanoNum Nat0 where
 eq Zero Zero = True
 eq (Succ0 m) (Succ0 n) = eq m n
 eq _ _  = False
 add m Zero = m
 add m (Succ0 n) = Succ0 (add m n)

instance PeanoNum Nat1 where
 eq One One = True
 eq (Succ1 m) (Succ1 n) = eq m n
 eq _ _ = False
 add m One = Succ1 m
 add m (Succ1 n) = Succ1 (add m n)

tl;dr: we can show that they are in fact isomorphic. Defining two different instances over them does not make them different. Defining two different functions over two types does not make them non-isomorphic! The instances are not describing an initial algebra structure, the data keyword is. As you say, the two instances play no role in the specification of the initial algebra.

In our example, we work with algebras
for the functor $1 + -$. That is, an algebra $A$ is given by a morphism $1 + A \to A$, or, in other words, an element of type $A$, which can be seen as a morphism $1 \to A$, and an endomorphism $A \to A$.

data Nat0 = Zero | Succ0 Nat0
data Nat1 = One | Succ1 Nat1

Here, Zero and One are the elements while Succ0 and Succ1 are the endomorphisms. We will see that they are isomorphic as F-algebras. A morphism $f$ between two F-algebras $A$ (with element $a$ and endomorphism $u$) and $B$ (with element $b$ and endomorphism $v$) is a $f \colon A \to B$ making the following diagram commute.

$$\require{AMScd}\begin{CD}
A+1     @>f+1>>  B+1\\
@VVa+uV        @VVb + vV\\
A    @>f>>  B
\end{CD}$$

And, in fact, we can find a pair of invertible morphisms making them isomorphic.
I will only define the first one, but the second one is analogous and checking that they are inverses should be easy.

$$\require{AMScd}\begin{CD}
\mathsf{Nat0}+1     @>f+1>>  \mathsf{Nat1}+1\\
@VV\mathsf{Zero+Succ0}V        @VV\mathsf{One + Succ1}V\\
\mathsf{Nat0}     @>f>>  \mathsf{Nat1}
\end{CD}$$

The commutativity of the diagram determines that the only possible $f$ must send Zero to One and Succ0 x to Succ1 x. This translates into code as follows.

f :: Nat0 -> Nat1
f Zero = One
f (Succ0 x) = Succ1 x

Precisely because $A$ is initial, this is the only possible $f$ making this diagram commute. We had no choice when defining $f$ (apart from undefined or any other of the constructions that make this kind of categorical reasoning fail in Haskell).

What about the two instances? They define two different functions over each one of the types, but that does not make them non-isomorphic as algebras. As you say, the instances play no role on the definition of the two algebras. The algebra structure concerns only the $1+A \to A$ morphism, not the two additional morphisms $A \times A \to A$ and $A \times A \to \mathsf{Bool}$ that define the instance. Even if we call the two different functions add, the second one is simply a different function. We could rename the second add, and we would see that they are, essentially, two different instances of the same class for (essentially) the same type.

What if we want an "add" (a binary) function to be part of the algebra? Then we would be looking for the initial algebra for the functor $F(X) = 1 + X + X \times X$, and neither Nat0 nor Nat1 (with their respective add functions) are initial algebras for this functor. The initial algebra would be the following one.

data Foo = Zero | Succ Foo | Add Foo Foo

What if we also want an "equality" function to be part of the algebra? There may be a better approach for this, but we can consider algebras on the category whose objects are pairs of types. An algebra is of the form $F(A,B) \to (A,B)$ for some endofunctor $F$, and in this case, we consider algebras of the form $(1 + A + A \times A, A \times A) \to (A,B)$. The natural numbers ($A$) and the booleans ($B$) endowed with zero $1 \to A$, the successor function $A \to A$, addition $A \times A \to A$, and the equality function $A \times A \to B$ would be an algebra of this form, but not the initial algebra. I think the initial algebra in this case could be written in Haskell as follows.

-- Initial algebra (where the object is a pair of types!).
data A = Zero | Succ A | Add A A
data B = Equ A A

-- Given any other algebra.
data C
data D
z :: C
s :: C -> C
a :: C -> C -> C
e :: C -> C -> D

-- There is a unique morphism (two morphisms) from the initial
-- algebra making the relevant diagram commute.
u1 :: A -> C
u1 Zero = z
u1 (Succ x) = s (u1 x)
u1 (Add x y) = a (u1 x) (u1 y)

u2 :: B -> D
u2 (Equ x y) = e (u1 x) (u1 y)

Where the relevant diagram is the following one.

$$\require{AMScd}\begin{CD}
(1+A+A\times A,A \times A)    @>>>  (1+C+C\times C,C \times C)\\
@V(Zero+Succ+Add,Equ)VV        @VV(z+s+a,e)V\\
(A,B)    @>(u1,u2)>>  (C,D)
\end{CD}$$


Number of words in the regular language $(00)^*$ According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation

$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$.

The language $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ is regular ($(00)^*$ matches it). $s_L(n) = 1$ iff n is even, and $s_L(n) = 0$ otherwise.

However, I can not find the $\lambda_i$ and $p_i$ (that have to exist by the above). As $s_L(n)$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of summands like in a Taylor expansion. Can anyone enlighten me?

For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.


Will $L = \{a^* b^*\}$ be classified as a regular language? Will $L = \{a^* b^*\}$ be classified as a regular language?

I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?

A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language?

A well-known result (that is proved in many textbooks) states that the language of a regular expression is regular. Since $a^* b^*$ is a regular expression, its language must be regular (if you believe this result).

Finally, to answer your question (what difference does the Kleene star make): in the language $\{a^n b^n : n \geq 0\}$, we need to count the number of $a$s and $b$s; in the language $a^*b^*$ we don't.


Can joins be parallelized? Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

EDIT: to bring some clarifications from the comments into this post:

We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each set
If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?

$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.


What is the difference between an algorithm, a language and a problem? It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and considering problems? And how do these relate to the concept of a language in formal language theory?

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word.

Language: a language is simply a set of strings. If you have an alphabet, such as
$\Sigma$, then $\Sigma^*$ is the set of all words containing only the symbols in $\Sigma$.
For example, $\{0,1 \}^*$ is the set of all binary sequences of any length.
An alphabet doesn't need to be binary, though. It can be unary, ternary, etc.

A language over an alphabet $\Sigma$ is any subset of $\Sigma^*$.

Problem: A problem is some question about some input we'd like answered. Specifically, a decision problem is a question which asks, "Does our given input fulfill property $X$?

A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language.
For a problem $X$, the corresponding language is:

  $L = \{w \mid w$ is the encoding of an input $y$ to problem $X$,
  and the answer to input $y$ for problem $X$ is "Yes"  $ \}$

Determining if the answer for an input to a decision problem is "yes" is equivalent to determining whether an encoding of that input over an alphabet is in the corresponding language.

Algorithm: An algorithm is a step-by-step way to solve a problem. Note that there an algorithm can be expressed in many ways and many languages, and that there are many different algorithms solving any given problem.

Turing Machine: A Turing Machine is the formal analogue of an algorithm. A Turing Machine over a given alphabet, for each word, either will or won't halt in an accepting state. Thus for each Turing Machine $M$, there is a corresponding language:

  $L(M) = \{w \mid M$ halts in an accepting state on input $w\}$.

(There's a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes $\mathsf{R}$ and $\mathsf{RE}$.)

The relationship between languages and Turing Machines is as follows

Every Turing Machine accepts exactly one language
There may be more than one Turing Machine that accept a given language
There may be no Turing Machine that accepts a given language.

We can say roughly the same thing about algorithms and problems: every algorithm solves a single problem, but there may be 0, or many, algorithms solving a given problem.

Time Complexity: One of the most common sources of confusion between algorithms and problems is in regards to complexity classes. The correct allocation can be summarized as follows:

An algorithm has a time complexity
A problem belongs to a complexity class

An algorithm can have a certain time complexity. We say an algorithm has a worst-case upper-bounded complexity
$f(n)$ if the algorithm halts in at most $f(n)$ steps for any input of size $n$.

Problems don't have run-times, since a problem isn't tied to a specific algorithm which actually runs. Instead, we say that a problem belongs to a complexity class, if there exists some algorithm solving that problem with a given time complexity.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $\mathsf{P}$, but if there's a polynomial-time algorithm solving a given problem $X$, then $X$ is in $\mathsf{P}$. There could also be a bunch of exponential-time algorithms accepting $X$, but since there exists a single polynomial-time algorithm accepting $X$, it is in $\mathsf{P}$.


Why is $AF \phi \lor \varphi$ not equivalent to $AF \phi \lor AF \varphi$? Can someone explain to me (perhaps with an example) why $AF (\phi \lor \varphi)$ is not equivalent to $AF \phi \lor AF \varphi$. This seems counter-intuitive, because in any path where $\phi$ (or $\varphi$) is true, $\phi \lor \varphi$ is true as well. Or is my reasoning wrong?

Thanks

You also need to argue the other way around. "Each path has either $\psi$ or $\varphi$" is not the same as "either each path has $\psi$ or each path has $\varphi$".


Comparative study between Deep neural nets and Bayesian Networks Is there any comparative study that showcases the powers of Bayesian Networks and Deep learning in their respective favorable setup and how they compare?

I tried to go through blogs but couldn't find out any experimental study where the respective models where described based on a example?

Rationale in putting this question: I am planning to work on Bayesian networks and I know they are great for inference and answering complex queries. But I couldn't find any convincing experimental results where they seemed to be more favorable as compared to other sophisticated machine learning tools like deep neural nets or conventional deep neural nets.

They're not directly comparable.  They do different things.  They solve different problems.

A Bayesian network is a probabilistic model of the relationship between multiple random variables.  It is a generative model.  It builds a model of the joint probability distribution between multiple random variables.  It typically requires some priors or assumptions about the structure of the joint distribution.  While it could be used for classification, it normally isn't.

Deep learning is typically used for classification: supervised learning.  It is a discriminative model.  It does not try to model/estimate the joint probability distribution between multiple random variables.  It typically does not require you to specify priors or assumptions about the structure of the joint distribution.


Are there infinite possibilities to the outcome of the P vs. NP question? The P vs. NP poll provides 3 possibilities: equal, not equal, and independent. This is reasonable, because despite the law of the excluded middle you must supply a proof for your answer, which itself is insufficient. But then the statement "P vs. NP is independent" itself can be independent, with a proof. And this process can go on indefinitely. One of them must be provable, or did I miss something? Anyway the number of possibilities is infinite, instead of 3. Is this correct?

This isn't really a question about P vs. NP - any other statement would do in its place. The point is that there are a couple different "philosophical contexts" being mixed up here, and depending on exactly how you ask the question each of $2$, $3$, or infinity are reasonable answers (I'm not claiming that these are exclusive, but I think they frame the question well):

The Platonic: If we adopt a certain measure of Platonism (for P vs. NP, something like "the natural numbers exist objectively even if our understanding of them is limited") then yes, every statement is either true or false. Provability from a given theory is a purely secondary matter, and the independence of a statement from (say) ZFC has no bearing on its truth.
The formalist: If we don't want to make any philosophical commitments, the most we can ask is whether the statement is provable in a given theory. Once we fix a single theory of interest - say, ZFC - the formalist version of the question does indeed boil down to three possibilities: our statement is either provable in that theory, or disprovable in that theory, or independent of that theory. (Or the theory is inconsistent, in which case the first two options hold simultaneously.)

Wildness of the type you're asking about emerges when we ask the "broader" formalist question: which theories is our statement provable in? When asked this way we do indeed get a wild situation, since for any interesting statement there will be some theories which prove it and some theories which disprove it. Note that this is really a more "stable" perspective than focusing on a single theory, but in practice mathematicians tend to prefer a single background theory so we can ignore foundational considerations which aren't really germane to the specific mathematics at hand.

Of course this conflicts with the language we often use in actual practice. The "true/false/independent" trichotomy blurs the Platonic and formalist contexts by conflating a fixed theory - usually ZFC - with "truth." This is a common practice, but is at best raising the question of why we assign privileged status to ZFC specifically (why not ZFC + an inaccessible? or ZF? or ZC? or ...). Ultimately it's just a linguistic convention: we recognize that in many situations, in order for our everyday mathematical language to be truly accurate we need to implicitly understand "true" as an abbreviation for "provable in ZFC."


Can someone tell a formal definition for this problem: k-disjoint triangle? k-disjoint triangle
"We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. "
The above definition is the best I could find online. Nowhere could I find an clear formal definition.

What does it mean to be vertex disjoint exactly?
How to prove k-disjoint vertex is NP hard?

Finding $k$ disjoint triangles in a graph means that you color $3k$ vertices with $k$ colors, $\chi_i, 1 \leq i \leq k$ such that for each color $\chi_i$, the graph $G[X_i] \simeq K_3$, where $X_i$ are the three vertices that received color $\chi_i$.
It simply means that you cannot use the same vertex in two different triangles.
This type of problem is often referred to as $K_3$-packing or triangle-packing: You want to "pack" as many triangles as possible in a graph $G$.
The problem is NP-complete even if you are given a tri-partition of the graph, and this problem is called 3-dimensional matching, one of Karp's 21 NP-complete problems.


Set containment of MinimumBadPrefix and BadPrefix of a Safety Property This question is related to formal model checking theory, but I cannot find a tag for it.

Let $P_{safe}$ be a safety property.

$BadPref(P_{safe})$ is the set of bad prefixes for $P_{safe}$

A Safety property $P_{safe}$ over Atomic Proposition $AP$ is regular
if its set of bad prefixes is a regular language over $2^{AP}$

Is the following true?

If $L$ is a regular language with $MinBadPref(P_{safe}) \subset L \subset BadPref(P_{safe})$,
then $P_{safe}$ is regular.
If $P_{safe}$ is regular, then any L for which
$MinBadPref(P_{safe}) \subset L \subset BadPref(P_{safe})$ is regular.

My attempt to 2. is that it's true

$P_{safe}$ is regular then $MinBadPref(P_{safe})$ is regular and so is $BadPref(P_{safe})$. A NFA $N$ recognizing $BadPref(P_{safe})$ can be obtained by adding self loops on the final states of the NFA $M$ recognizing $MinBadPref(P_{safe})$. And $L$ is recognized by some NFA containing a subset of the self loops added to $M$. Therefore $L$ is regular.

And what about 1.?

For (1), I will only give a sketch at first, in case you want to work it out yourself; I can add some details later if you want. Try proving the following:

$w\in BadPref$ if and only if $w$ has a prefix $u$ which is in $L$.

(2) is already covered quite well by David's comments.


How is density of a substance in grams per cubic centimeter a discrete attribute? I'm going over the different types of attributes in data-mining (nominal, ordinal, discrete, etc) and there is one example in the book that states that the density of a substance in grams per cubic centimeter is a discrete attribute. Why is this? I confuses me that this is the case but it also says that the distance from the center of campus is continuous.

The book is wrong.  Density is continuous.  It could be any real number.  You are quite right.


Find amortized cost for insertion in binary arrays using accounting/potential methods? Background:

The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. However, there will be no relationship between the items in different arrays. The issue of which arrays are full and which are empty is based on the binary representation of the number of items we are storing. For example, if we had 11 items (where 11 = 1 + 2 + 8), then the arrays of size 1, 2, and 8 would be full and the rest empty.
For inserts, we'll do them like mergesort. To insert the number 10, we first create an array of size 1 that just has this single number in it. We now look to see if $A_0$ is empty. If so, we make this be $A_0$. If not (like in the above example), we merge our array with $A_0$ to create a new array (which in the above case would now be [5, 10]) and look to see if $A_1$ is empty. If $A_1$ is empty, we make this be $A_1$. If not (like in the above example) we merge this with $A_1$ to create a new array and check to see if $A_2$ is empty, and so on.

Further clarification found here.

To be clear about costs, let’s say that creating the initial array of size 1 costs 1, and merging two arrays of size $m$ costs $2m$ (so merging the sorted arrays can be done in linear time).

The claim is that the above data structure has amortized cost $O(\log n)$ per insertion.

How to show this using the accounting and potential methods for amortization?
What would potential function be?

Initial ideas: Right off the bat it seems that this problem bears a lot of resemblance to the typical binary counter problem. Imagine each array being empty or filled represented by a value of 0 (empty) or 1 (filled), and these values are updated accordingly with insertions. These counters would change when current arrays are completely filled and have to perform merges, which will create a larger filled array and as a consequence several smaller unfilled arrays, changing a lot of 1s (filled) to 0s (unfilled). In the binary counter example the expensive cost of incrementing is dealt with through the potential function which is the number of 1s in the binary counter. The cost for an insertion here is not just incrementing a counter, but paying for costly merges. I do think the idea of a counter perhaps can tie into this problem, but am unsure how it connects to potential method and $O(\log n)$ per insertion. Any thoughts?
Also, found this explanation but it doesn't fully make sense to me. Maybe someone would be willing to elaborate?

Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n < 2^{k+1}$. Thus only the arrays $A_0,\ldots,A_k$ are active. The cost of the $m$th operation can be broken down as follows:

Creating the initial array: 1.
If the number of elements (before adding the current one) is odd: 2.
If the number of elements is $3\bmod{4}$: 4.
And so on.

Observe now that:

The number of odd numbers among $0,\ldots,n-1$ is $\lfloor n/2 \rfloor$.
The number of elements $3\bmod{4}$ among $0,\ldots,n-1$ is $\lfloor n/4 \rfloor$.
And so on.

We conclude that the total cost of the first $n$ operations is
$$
\begin{align*}
&n + 2\lfloor n/2 \rfloor + 4\lfloor n/4 \rfloor + \cdots + 2^k \lfloor n/2^k \rfloor \\ \leq
&n + 2(n/2) + 4(n/4) + \cdots + 2^k(n/2^k) \\ =
&n + n + n + \cdots + n \\ =
&(k+1) n \\ =
&(\lfloor \log_2 n \rfloor + 1)n.
\end{align*}
$$
We conclude that the amortized cost is at most $\log_2 n + 1 = O(\log n)$.


Complexity of calculating independence number of a hypergraph Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may contain more than two vertices.

An "independent set" (http://en.wikipedia.org/wiki/Independent_set_(graph_theory)) is a collection of vertices, $U$, that does not fully contain any of the hyperedges:  $e_i\not\subseteq U$.  The "independence number" or "maximum independent set size" is the size of the largest independent set in the graph $G$.

I know that finding if there is an independent set of size $k\in\mathbb{N}$ in some normal graph $G$ is NP-Complete.  If I am not mistaken, this holds for hypergraphs as well.  However calculating the independence number is not proven to be NP.  Even approximating it is not proven in NP.

First, is there a more specific complexity class for calculating the independence number than NP-Hard?

Second, how much harder is it for a hypergraph?  Again, is there a complexity class more specific?

For related questions, a recent dissertation has been helpful to me: https://escholarship.org/uc/item/79t9b162.

Thanks!

did not find a proof of complexity class harder than "NP hard" for this problem (ie the presumably more complex hypergraph version of the problem does not seem to have been proven harder than the graph version) however did find the following. Saket has recent research in the area. results in complexity theory in active areas of research tend to be highly specialized and in the form "for limited hypergraph types [x], the following improved complexity bound [y] is shown." (ie more as approximability results, & more specialized than what you request but it can be mined for nearest desirable results/refs.)
basically hypergraphs while an old mathematical concept are a more recent area of complexity theory research and there is a large active/ongoing research program of determining complexity of operations around them and how those complexities relate to corresponding graph operation complexities, and translating theorems and knowledge about graphs into their hypergraph analogs.

Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisﬁable CSPs Saket (Dec 2013)

This work revisits the PCP Veriﬁers used in the works of H˚astad [H˚as01], Guruswami et al. [GHS02],
Holmerin [Hol02] and Guruswami [Gur00] for satisﬁable MAX-E3-SAT and MAX-Ek-SET-SPLITTING,
and independent set in 2-colorable 4-uniform hypergraphs. We provide simpler and more efficient PCP
Veriﬁers to prove ... improved hardness results ...

Hardness of Maximum Independent Set in Structured Hypergraphs Saket powerpoint slides overview


Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:

Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets dynamic.

I felt a bit odd after reading the statement that "set" in Mathematics and in CS are different from the mutable point of view. Now in Mathematics what we deal with are theoretical aspect of things and as such "set" is a theoretical concept and so it is in Theoretical CS. If it is immutable in mathematics then so it is in CS. Mathematics and Theoretical CS are interlinked. So given a graph algorithm which say finds the minimum shortest path between a pair of vertices , we can't say whether it belongs to Mathematics or CS.
Often in algorithms we write statements as :
$$S  = S \cup \{a\} \quad \text{view $1$}$$
Which seems to sort of change our set $S$, but if we look it in this way:
$$S'= S \cup \{a\} \quad \text{view $2$}$$
$$S=S'$$
So in the second situation we are not modifying our actual set $S$ we are forming a new set $S'$ with $S$ augmented with $a$ and then after that we are making the variable $S$ refer to $S'$.
What I feel is that the concept of the set being mutable or immutable is solely dependent on the data-structure of representation of the abstract concept of "sets" and since in data-structure the two steps in view $2$ are combined and implemented, so they are called dynamic sets.
In short I feel that Dynamic Sets are data-structure implementation of sets and not the abstract sets.

Set are at a higher level of abstraction than algorithms.  You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc.
Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to describe specifications but not algorithms.
They're also used do describe algorithms in functional programming (see e.g. Purely Functional Data Structures by Chris Okasaki ) but that is not very common in literature as most algorithms are described in terms of ephemeral data structures.
To answer your question, sets are the same both in Mathematics and CS, they're immutable.   Dynamic sets is a data structure loosely related to sets.
The author is not saying that sets are different in CS than in Mathematics.  He's saying that the data structures, as commonly described in algorithms are mutable.  CS is much more than algorithms and data structures.


Language of particular CFG Let:
$ G = <V, \Sigma, R, S >: \\
V = \{ S,A,B,C \} \\
\Sigma = \{0, 1\} \\
R: \\
S \to CSC|A \\
A \to 0B1|1B0 \\
B \to CB|\epsilon\\
C \to 1|0
$

I need to find the language (no need to formally prove).
I have written many words but cannot seem to find a rule.
After trying that path I rewrote the grammar in a shorter rules:

$$
S \to 0S0|0S1|1S0|1S1|0B1|1B0 \\
B \to 1B|0B|\epsilon
$$

What should be my way of finding any pattern? to go each possible path independently ?

First, let us notice the following:
$$
L(S) = \{ xyz \mid x,z \in \{0,1\}^*, |x|=|z|, y \in L(A) \} \\
L(A) = 0L(B)1 \cup 1L(B)0 \\
L(B) = (0+1)^*
$$
Putting everything together, we get
$$
L(G) = \{ x\sigma y \tau z \mid x,y,z \in \Sigma^*, \sigma,\tau \in \Sigma, |x|=|z|, \sigma \neq \tau \}
$$
In other words, a word $w$ is in the language if there exists $i \leq |w|/2$ such that the $i$th symbol from the left is different from the $i$th symbol from the right. The condition $i \leq |w|/2$ can be eliminated, and we get that for some $i$, the $i$th symbol of $w$ is different from the $i$th symbol of $w^R$. In other words, $w \neq w^R$.

So your grammar generates the language of non-palindromes.


Set of steps that cannot be implemented on a Turing machine Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?

The Church–Turing thesis states that every algorithm can be implemented on a Turing machine. It has stood the test of time. In particular, I believe that the answer to your question is negative.

The appearance of quantum algorithms, in particular Shor's factorization algorithm, has called into question the efficient Church–Turing thesis (sometimes known as the Cook–Karp thesis), which states that $\mathsf{P}$ captures the class of efficiently solvable problems; but quantum computers are known to compute the same class of languages as classical computers.


Finding invariant when detecting a cycle Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is :

Create an array : seen of size $\mid V \mid$ with seen[i] = false for all $i$

Perform a DFS (or BFS) starting at the node $0$.

When we see a node $i$ : we have two cases : if seen[i] = false then seen[i] = true else we found a cycle.

One idea to prove the correction of this algorithm is saying the following : if the algorithm return true it means there two  nodes $x$ and $y$ such that when we looked at $y$ we have : seen[y] = false and seen[x] = true thus there is a cycle namely the cycle which begin at $x$ and use the only path that connect $x$ and $y$ in the DFS tree and then use the edge $(y,x)$.
The problem is that this is not really rigourous and I am really lokking for an invariant that we help me do the correction of this algorithm rigourously.
So is there any invariant I can use here ?
Thank you very much  !

Assuming we execute line 3 when you first visit a node, and assuming you are working with directed graphs, this algorithm is incorrect (consider what happens with a cross edge discovered by DFS).

Alternatively, assuming you are working with undirected graphs:

The missing part of your argument is the "thus" part; why does the existence of two such nodes imply the existence of a cycle?

To work out the proof, I suggest categorizing what types of edges can exist in the search tree for an undirected graph: tree edges? forward edges? back edges/ cross edges?  Then, categorize what type of edge caused you to visit x when seen[x] was true.  What does that mean the search tree has to look like?


NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time? As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified in polynomial time. Let's say we have a problem $K$ in NP and we have a certificate $c_e$ obtained externally that proves a YES or NO result for $x$.
From my understanding of the proof implications, if we have a NTM which solves $K$ in polynomial time, this implies that there exists a verifier for $K$ which takes any certificate and says whether that specific certificate is a valid "solution" for if $x$ results in YES/NO. The proof involves the fact that the NTM generates its own certificate $c_n$ which the verifier then uses, but this has nothing to do with $c_e$ from what I see. From my understanding, the verifier should take any arbitrary certificate (including $c_e$) and verifies that it indeed leads to the answer. But instead, the verifier uses only the certificate $c_n$ created by the NTM to verify whether $x$ results in YES/NO. In other words, the verifier isn't able to check any arbitrary certificate - it's only able to check the one created by the NTM.
To rephrase in case I'm not making sense – constructing a verifier, in my interpretation, means this verifier can take any certificate and check whether it's a proof for $x$. But the equivalence proof has the verifier take a specific certificate $c_n$ created by the NTM and only checks whether that is a valid proof for $x$. So what makes the verifier able to  verify for any arbitrary certificate $c_e$?
I must be getting confused somewhere. Is there any point which labels my misunderstanding? I'd really like to fully grasp the intuition of the proof.

A non-deterministic Turing machine has a special instruction that allows it to non-deterministically "guess" a bit. The list of bits guessed by the machine is sometimes called a certificate. You can imagine that the guessed bits are taken from an auxiliary tape, whose contents you can think of as a certificate.

Here is an example. Consider the problem SAT: the input is a formula, and wish to find out whether the formula is satisfiable. A non-deterministic Turing machine for this problem "guesses" an assignment, and then checks ("verifies") that it satisfies the given formula. Alternatively, the machine gets a certificate and verifies that it is a satisfying assignment for the input formula. This is exactly the same Turing machine, only the process of non-deterministic guessing is visualized as reading from an auxiliary input, which we think of as a certificate.