Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)? Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.
Then, that language/set is decidable. Because it is trivial to devise a (halting) TM_R, using TM_G, that recognize/accepts the words/numbers of that language/set.
It is also clear (really?), that there must be a non-contracting grammar for the language of TM_G.
Now, let's suppose a we have a TM_G' that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM_R' that completely recognizes it. Now, it is not clear how to build TM_R' using TM_G' (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM_R' based on TM_G').
In any case, by assumption, TM_R' (the halting/complete recognizer) does exist. Then, we can use TM_R' to build a TM_G'' which generates the language in lexicographical order.  Hence (really?), there exists a non-contracting grammar for the language.
In sum, is the class of decidable languages equivalent to non-contracting grammars?
In other words, are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?
Expressed in terms of Turing Machines: **is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? **

Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: diagonalization. Any time we have a class of decidable languages for which we have a "decidable syntactic description" (I'm being vague about this for a moment), we can diagonalize out of this class to get a decidable language not in the class. Basically, we whip up a notion of "$n$th language in the class" and then consider the new language which contains word $1...1$ ($n$ times) iff the $n$th language in the class does not contain that word (or something similar); granting the complexity assumption on the starting class, this results in a decidable language.
(In snappier computability-theoretic terminology: if $f(x,y)$ is a total computable function then there is a total computable $g(z)$ such that for each $x$ there is some $y$ with $f(x,y)\not=g(y)$.)
Classes like type $1$ grammars are defined by simple syntactic conditions, and so can be diagonalized out of. Of course this does not necessarily result in a natural example of a decidable language not in the starting class, but it does prove that that class misses many decidable languages.


Can you reduce every decidable language to a regular language? One of my previous questions on an exam was the following

Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language).
If so, does this mean that you can reduce every CFL to a regular language?

The reductions are all referring to many-one reductions. My intuition tells me that this is possible as all regular languages are also decidable.

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then:

if $x \in A$, the reduction outputs $y_{in}$
if $x\notin A$, the reduction outputs $y_{out}$

where $y_{in}$ and $y_{out}$ are constant words in $B$ and $\overline{B}$, respectively.


Deleting in Bloom Filters I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete operation--for example: counting Bloom filters. I heard also about another method, which uses a second filter. If I want to remove an element I have to 'insert' it into this second filter. I can't find how this proposed structure operates, any article about it, or even the name of the originator. Maybe someone can share with me with a link to any interesting articles about this method? I found a lot of articles about counting Bloom filters and other methods, but I can't find any description of this one.

I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions.

As this is a very simple solution, it might be considered as a folklore.

Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems):

http://www.dca.fee.unicamp.br/~chesteve/pubs/bloom-filter-ieee-survey-preprint.pdf

Search for:

  Removal of an element can be implemented by using a second Bloom ﬁlter that contains elements that have been removed

In the third section of this paper, you can read about many techniques to deal with deletion. Maybe you will find there some reference (again - I'm not sure there is some paper about it, as it is a simple idea).


Short Fibonacci Heap Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then why?

I faced this question in an interview but couldn't answer it. Hopefully can learn it from here.

Corollary 1 in Fredman & Tarjan's paper states:

  A node of rank $k$ in an F-heap has at least $F_{k+2} \ge \phi^k$ descendants,
  including itself; where $F_k$ is the $k$th Fibonacci number ($F_0 = 0$, $F_1 = 1$, $F_k = F_{k-2} + F_{k-1}$ for $k \ge 2$), and $\phi = (1 + \sqrt{5})/2$ is the golden ratio.

Any node of rank 4 must have at least $F_{4+2} = 8$ descendants including itself, but the root node in the example has only 5. Therefore it could not have been created using Fibonacci heap operations.


Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar? I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating push-down automatons from context-free grammars are not always phrased in the same way, with mostly two variations:

For the given grammar G, define a push-down automaton M such that L(M) = L(G)
For the given grammar G, define a push-down automaton M equivalent to grammar G.

In Introduction to Automata Theory Languages and Computation by John Hopcroft, in section 6.3.1 a method to obtain the equivalent push-down automaton for a context-free grammar is defined. Since the book is widely available and very well known, I will not copy the method here.

Of course, it is also possible to figure out the language produced by the grammar and work from there to define an automaton which accepts that language (this would be similar to the first phrasing).

These two method would produce equivalent automatons (i.e. automatons which accept the same language), but I am not sure if there is something that tells them apart.

Is there a theoretical difference between "the push-down automaton equivalent to a context-free grammar" and "the push-down automaton which accepts the language defined by a context-free grammar"?

The answer is really up to the definition of equivalent. The common definition is that two automata/grammars are equivalent if they define the same language. If your class uses the common definition, then both statements are entirely equivalent.


Why isn't TQBF part of the polynomial hierarchy? TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it?

I think this is incorrect because TQBF consists of any number of quantifiers, but each level in the PH has fixed number of quantifiers, so there's no level of the PH that can solve TQBF. Does it have to do with the fact that the number of quantifiers is part of the input in TQBF, whereas in PH only the formula is the input?

So this could also be worded as, if there exists a PH-complete problem, does TQBF reduce to that problem?

What you're missing is the distinction between QBF and 2QBF.

It's an open problem whether TQBF is contained in any level of the polynomial hierarchy, but it'd be reasonable to expect that TQBF is probably not contained in any level of the polynomial hierarchy.

TQBF is PSPACE-complete.  Also, if PSPACE = PH, then the polynomial hierarchy collapses.  Thus, if TQBF is in some level of the polynomial hierarchy, then so is all of PSPACE, and thus the polynomial hiearchy collapses.

It is conjectured that the polynomial hierachy does not collapse.  However, this is merely a conjecture, analogous to the conjecture that P $\ne$ NP; whether or not this is true is an open problem.

  TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$.

Giraffes consist of atoms.  So do light bulbs.  Therefore, every giraffe is also a light bulb.

What's wrong with that reasoning?  The same thing that's  wrong with your reasoning.

Check your definitions.  $\Sigma_n^2$ allows formulas that contain only two alternations of quantifiers, i.e., 2QBF.  QBF allows an unlimited number of alternations of quantifiers.  2QBF is complete for $\Sigma_n^2$; QBF is complete for PSPACE.


Count number of ways in which atomic operation(s) of n different processes can be interleaved PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion.
Suppose there are a total of n different processes - P1, P2, P3 .... , Pn.
Each process can have a variable number of atomic operation(s) that constitutes that process, but it should have at least one operation.

EXAMPLE

Consider two processes, P1 and P2

P1: 1o1; 1o2; 1o3; 1o4; 1o5; 1o6;
P2: 2o1; 2o2; 2o3;

where 1o1 denotes first operation of process P1.

Attempt:
Fix position of all operations of process P1, then count the number of ways in which the operations of process P2 can be placed in empty positions( __ ) created between operations of process P1, as shown below:

__ 1o1 __ 1o2 __ 1o3 __ 1o4 __ 1o5 __ 1o6 __
There are seven empty positions numbered 1 to 7.

Counting: (Note that the numbers below (like 1 2 3) denote the empty position number.)
> Case1: When all three operations of P2 are placed in consecutive empty positions.

  1 2 3

  2 3 4

  3 4 5

  4 5 6

  5 6 7

  We have a total of 5 ordering possible for empty positions.

> Case2: When operations of P2 are placed in two consecutive empty positions taken together.

  1 2 3   2 3 4   3 4 5   4 5 6   5 6 7

  1 2 4   2 3 5   3 4 6   4 5 7

  1 2 5   2 3 6   3 4 7

  1 2 6   2 3 7

  1 2 7

  First cell in every column has already been counted in previous case. We have a total
  of (5 - 1) + (4 - 1) + (3 - 1) + (2 - 1) + (1 - 1) = 10 ordering possible for empty
  positions.

  A similar argument can be made for last two consecutive empty positions taken together,
  that gives us a total of another 10 ordering possible for empty positions.

> Case3: These are those cases that do not have empty positions numbered 8 and 9 for them.

  6 7 8

  7 8 9

> Case4: When operations may crash mid way before completion.
  An 'x' denotes position where a crash is possible and process (here P2) terminates.

  1x 2x 3

  2x 3x 4

  3x 4x 5

  4x 5x 6

  5x 6x 7

  6x 7x 8

  7x 8x 9

  There is a total of 14 'x's possible.

  Note: I have not put a cross after last empty position number because I am assuming that
  a process will complete at this stage. You may correct my assumption if this is
  wrong and should not be assumed in the first place.

Adding all 4 cases: 5 + 2*10 + 2 + 14 = 41. There are 41 possible ways to interleave operations processes P1 and P2.

As you can see, counting like this is cumbersome and error prone. I have missed cases.
How can this counting problem be generalised? Please see the problem statement at the top of the question.


Multiple inputs in lambda calculus (Confusing example) In a programming class I take, we briefly (very briefly) touched lambda calculus. I think I have a pretty good grasp of the basics now, but one example given I just don't understand. Am I missing something or is the example possibly false?

$\lambda x.x \; (\lambda y.2*y) \; square \; 3$

The solution to this was $6$, because $\lambda x.x$ (the first function) is applied to $square$ (the first input) which just "disappears" and $\lambda y.2*y$ is applied to $3$, which gives us $6$:

$\lambda x.x \ (\lambda y.2*y) \ square \ 3 \implies (\lambda y.2*y) \ 3 \implies 2 * 3 \implies 6$

EDIT

Regardless of whether the "disappearance" of $square$ is correct, why would the first step be to apply $\lambda x.x$ to $square$ ? Instead of the whole expression, or just the part in parenthesis (which would, afaict, give the same result). I.e., what way of parenthesising is implied from the way it's written above?

/EDIT

The way I understand it, it should be either 18, because:

$\lambda x.x \; (\lambda y.2*y) \; square \; 3$ with parenthesis should be:

$(((\lambda x.x \; (\lambda y.2*y)) \; square) \; 3)$ which gives me:

$(((\lambda y.2*y) \; square) \; 3) \implies ((2*square) \; 3) \implies 2 * square(3) \implies 2 * 9 \implies 18$

or nothing at all, i.e. $((2*square) \; 3)$ doesn't make sense.

Another example that was given:

$(\lambda f.(\lambda x.f(f \; x))) \; square \; 3 \implies (\lambda x.square(square \;x)) \;3 \implies square(square \; 3) \implies square(9) \implies 81$

This second example seems clear to me, I'm just adding it to show something similar.

How would one properly solve $\lambda x.x \; (\lambda y.2*y) \; square \; 3$ ?

The problem is in (most likely wrongly) parenthesising expressions.

$\lambda$ abstraction goes as far right as it can, so your whole example is just one abstraction with body $x\ (\lambda y. 2 \cdot y)\ \texttt{square}\ 3$, meaning that there is nothing to be applied to $\lambda x$, thus no "level-0" redexes. There is just one redex in here, namely $\require{enclose} \enclose{horizontalstrike}{(\lambda y. 2\cdot y)\ \texttt{square}}$, reducing to $\require{enclose} \enclose{horizontalstrike}{(2\cdot \texttt{square})}$. There is also no redexes within the body because if we fully parenthesise the original expression (having in mind that $\lambda$ applications (within the body) are left associative) we get
$$\lambda x. \biggl(\Bigl(\bigl(x\ (\lambda y. 2 \cdot y)\bigr)\ \texttt{square}\Bigr)\ 3\biggr)$$

If we want to make it reduce to $6$, we must completely ignore $\texttt{square}$, because no natural number squared gives $6$. We can do that by making it an input to abstraction that doesn’t use it.
$$\bigl(\lambda x.(\lambda y.\ 2 \cdot y)\bigr)\ \texttt{square}\ 3$$


Is $\log(n-1) \in \Omega(\log(n))$? I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true.
Namely, is $\log(n-1) \in \Omega(\log(n))$?

As you have seen, $\log(n+1) \in \mathcal{O}(\log n)$. That means that $\log n \in \Omega(\log( n + 1))$. Now you can change $n$ with $n-1$ and have your answer.
To be more precise, $\log(\alpha n^{\beta} + \gamma) \in \Theta(\log n)$ for any $\alpha, \beta, \gamma \in \mathbb{R}_{>0}$.


Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$ Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$.
Hint:  Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a padding argument.

I proved that $L'=\{x\#1^{|x|^{\log|x|}}\mid x\in L\}$ is in $\mathsf{P}$ but I'm not sure how to conclude that $L\in\mathsf{P}$, or how do I get the contradiction to the assumption.

The proof is by contradiction. We assume that $\mathsf{P} = \bigcup_{k=1}^\infty \mathsf{DSPACE}(\log^k n)$, and reach a contradiction.
Let $L$ be any language in $\mathsf{DTIME}(n^{\log n})$. Thus there is a Turing machine for $L$ which runs in time $n^{C\log n}$, and in particular, uses space at most $n^{C\log n}$. Let $L' = \{ x10^{|x|^{C\log |x|} - |x| - 1} : x \in L \}$. Then $L' \in \mathsf{P}$, and so $L' \in \mathsf{DSPACE}(\log^k n)$, for some $k$. In terms of the true input size $m$, we have $n = m^{C\log m}$, and so $L \in \mathsf{DSPACE}(\log^k (n^{C\log n})) \subseteq \mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{P}$. This contradicts the time hierarchy theorem.


Proof that $P\subseteq NP$ without nondeterministic TM I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM.
If you answer please write with as much details as you can.

The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$.
Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing machine, it follows that $\Pi \in \mathsf{NP}$, i.e., $\mathsf{P} \subseteq \mathsf{NP}$.
However $\mathsf{NP}$ can be equivalently defined as the set of decision problems $\Pi$ for which there exists a poly-time verifier (a Turing machine) $V$ and a polynomial $p$ such that if $x \in \{0,1\}^*$ is an instance of $\Pi$, then there exists a certificate $c \in \{0,1\}^*$ of length $|c| \le p(|x|)$ such that $V(x,c)$ accepts if and only if $x$ is a yes-instance for $\Pi$.
Using this definition every problem $\Pi \in \mathsf{P}$ is also in $\mathsf{NP}$, since it suffices to choose $p(|x|)=0$, $c(x)=\varepsilon$ (where $\varepsilon$ denotes the empty word), and $V(x, c)$ as the Turing machine that simulates any poly-time decider $T$ for $\Pi$ and accepts iff $T(x)$ accepts.


Looking for the English name of algorithm using a precomputed array for interval sum computation I am looking for the English name of the following algorithm:

We are given an array a with numbers and we need to be able to efficiently retrieve the sum of a continuous interval [f,t] of numbers in that array. In order to do that we precompute an array sums(of size size(a) + 1) that stores the sums of the prefixes of the initial array. More formally sums[i] = a[0] + a[1] + ... a[i-1]. This array can be constructed with linear complexity and now in order to compute the sum of the numbers in the interval [f,t], we simply compute sums[t]-sums[f-1].

Direct translation of the name of the algorithm(or more precisely the datastructure) that I've seen used in Bulgaria is prefix array, but in my experience direct translation often turns out to be wrong when it comes to algorithms and data structures.

How is this algorithm(or datastructure) called in English?

I think the array sum is the result of the prefix computation of the original array (link).


Find an infinite set of strings that are compressable better than in $O(\log n)$ space The task is to find an infinite set of strings $a_1,a_2\ldots$, where $|a_{i+1}|>|a_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a_i)|=o(\log_2 |a_i|)$ with $i\to\infty$.

I have considered a set of strings with minimal entropy: $a_1=b, a_2=bb$, etc. The optimal compression algorithm for these strings is $f : a_i\mapsto |a_i|$, but this compresses each string only to $O(\log i)$ space.

Hint:

   Instead of $a_i = b^i$, try $a_i = b^{f(i)}$ for some function $f$.


Where is the ambiguity in this grammar? I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the same sentence using different parse trees. After looking at it for a while, I can't find the sentence/parse trees that show the ambiguity.

s ::= a

a ::= a a | A | B | C

More a tip than an answer, but it should get you to the solution:

Try to produce a word with 3 terminal symbols. Can you find more than one syntax tree for the same word?


Sort huge file algoritm What algorithm should be used here to solve this problem efficiently?

One file stores 5 year log of user IDs & their website visit dates in random order. There were around 1,000,000 users on the website and 1/4 of them were active. Active users visited the website 100 times a day on average.

You need to create a new file in which user IDs would be sorted in ascending order. For the same user IDs records should be sorted by their visit date in ascending order.

Input example:

1234567890 2013-03-08 12:26:09
0987654321 2013-03-09 09:23:17
1234567890 2014-01-01 00:00:34
0087645544 2015-02-03 17:45:01
0087645544 2015-01-03 11:05:06

Output should be:

0087645544 2015-01-03 11:05:06
0087645544 2015-01-03 17:45:01
0987654321 2013-03-09 09:23:17
1234567890 2013-03-08 12:26:09
1234567890 2014-01-01 00:00:34

What I've tried so far:

From what I've yet found out, the External Sort algorithm should be used here. But how exactly, there are different types of it (2-way, k-way etc)? And how do I apply it to the second column (which is visit date)?

I suppose the file is too large to fit in the main memory at once. In this case a basic solution is to divide the file into small enough parts so that you can sort each part individually in memory using any standard sorting algorithm. You can then merge the parts by placing a pointer to the start of each file and repeatedly advancing the pointer with the smallest element, collecting the elements into one big sorted file (you can keep track of the minimum using a heap data structure). This is called a $k$-way merge, where $k$ is the number of parts. If the heap does not fit into the main memory, then we can merge just $k' < k$ files at a time, and then merge $k'$ of the merged files at a time, then merge $k'$ of those, and so on, until only one file remains.

I think this is more or less what the Linux sort command does for large files. It can also handle keys consisting of multiple columns. Check the manual of the program for the details.


Is function with finite amount of $\Phi_x(x+1)$ occurrences Turing computable? I'm studying for my exam from Logic and Computability and we have to face following kind of examples:

$$f(x) = \begin{cases}
         \ 1 &\text{if }\Phi_x(x+1)\!\downarrow\text{ and }x\leq50\\
         \ 0 &\text{otherwise.}
\end{cases}$$

Unfortunatelly I'm not really clear on how to tackle those. $\Phi_x$ is the $x$-th computable function, thus it's also Turing computable. This implies, there exists a TM (we have $N$ of them) which halts and returns the output.

The task is to determine whether it's computable. In order to prove it we either provide an informal algorithm to show it's computable or a formal proof that it's not. Can any of you solve this example?

If $f(x)$ is computable, then $\Phi_x$ needs to halt for every $x \in\{1, \dots, 51\}$. However $\Phi_x$ could be undefined on one of the elements from $\{1, \dots, 51\}$ and keep looping forever.

At the other hand, there is an upper bound on $x$, which indicates its computability.

Please, can you show me the right direction?

Thanks!

You can compute this function using a table of size 51. More generally, if $f$ is a function which differs from a computable function $g$ on a finite number of inputs, then $f$ is computable as well. In our case, $g$ is the constant zero function, which is trivially computable.


Open question regarding the DFS It is an open question that whether $\mathsf{DFS\text{}}$ can be done in $O(m+n)$ time and $O(n)$ bits of space, where $n,m$ represent the number of vertices and edges in a undirected graph. see this for DFS

DFS for directed graph is known to be in RNC i.e. randomised NC. $\mathsf{DFS\text{}}$ also known to be $\mathsf{P\text{-}Complete}$ problem.

My question is what would happen if someone shows that  $\mathsf{DFS\text{}}$ can be done in $O(n+m)$ time and in $O(n)$ bits of space?Is it likely in that situation for DFS to admit polyloga-rithmically fast, parallel algorithm using only polynomial resources (see this research paper)?

It is conjectured that $\mathsf{P} \neq \mathsf{NC}$, and so no $\mathsf{P}$-complete problem has polylogarithmic parallel algorithms. This in no way contradicts the existence of a linear time and space algorithm for DFS.


Push relabel algorithms in flow networks In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$$
\sum_{u \in U}e(u) \;=\;
\sum_{u \in U}\;\sum_{v \in U}f(v, u) \;+\;
\sum_{u \in U}\;\sum_{v \in \bar{U}}f(v, u) \;-\;
\sum_{u \in U}\;\sum_{v \in U}f(u, v) \;-\;
\sum_{u \in U}\;\sum_{v \in \bar{U}}f(u, v)
$$

where $f(u, v)$ is the flow between vertices $u$ and $v$, $e(u)$ is the excess flow at a particular vertex, $U$ is the set of vertices which are reachable from the source, and $\bar{U}$ is the set of remaining vertices.

In the next line, the first and third terms disappear. I don't understand why that holds. I do realize that those are flow values from vertex $u$ to vertex $v$ where both of them are in the same set $U$, but I don't understand why they cancel out to zero.

You just have to reorder the elements of $U\times U$, because the double sum contains each edge $(u,v) \in U\times U$ exactly once:

$$\sum_{u \in U}\sum\limits_{v \in U}f(v, u) =
\sum_{(u,v) \in U\times U}f(v, u) =
\sum_{(u,v) \in U\times U}f(u, v) =
\sum_{u \in U}\sum\limits_{v \in U}f(u, v)$$

The fist sum sorts the edges by their first vertex, the third sum (of the question's equation) sorts the edges by their second vertex. This is the simplest imaginable form of a double counting argument.


Big O notation and "input" Suppose I have an algorithm that reads lines in a file(linear) and for each line in the file, it sorts each word(nlogn).  This algorithm is mnlogn, where m is the number of lines and n is the number of characters in a word.

Asymptotically, as the file gets longer the number of lines becomes small in comparison to the number of characters, so the running time of this algorithm is O(nlogn)?  How do you determine big O like this where the inputs are different?

The asymptotic running time of your algorithm is $O(mn\log n)$, as you mention. If we don't know anything further about $m$ or $n$, there is no way to simplify this. If you know that $m = O(f(n))$, then the running time is also $O(f(n)n\log n)$. For example, if you know that $m = O(\sqrt{n})$, then the running time is also $O(n^{1.5}\log n)$. It will be $O(n\log n)$ only if $m = O(1)$, that is, $m$ is constant.


turing machine for the language L ={w#w' where w<w'} I'm blocked with a question for a long time.

L ={X=w#w' where w < w' and w,w' in {0,1}* }

So i'm trying to find :

1-a deterministric turing maching for the language L.

2-a non deterministic for L.

example :

      w=01 w'=111 --> X in L.

      w=1 w'=011 -->  X is **not** in L.

For the deteministic machine , i have an idea only when |w|=|w'|, it's only comparing an alphabet in the first word with an alphabet in the second word.

but i don't know how to solve it when we have two different length ; like my second example .

Do you have any idea for the turing machine?

Thank you.

Here is a sketch of a construction method of the TM:

Compare bit by bit from the first bit to the last bit as normal. If equals, proceed to the next bit. Otherwise, it can decide the order.
If the head of TM reaches the word separator $\#$ or the blank symbol (say $\$$ or something), finish the comparison. If both words end simultaneously (i.e. when $\left| w \right| = \left| w' \right|$), then $w = w'$. If not, the shorter word is less than the other in the lexicographic order.

This idea is the same for both a deterministic TM and a non-deterministic TM. Only a non-deterministic TM can compare bits in a non-deterministic way.


Is the sum $f+g$ of two one-way-functions a one-way-function? Since there exists a bijection of sets from $\{0,1\}^*$ to $\mathbb{N_0}$, we might view one-way-functions as functions $f :\mathbb{N_0} \rightarrow \mathbb{N_0}$. My question is, suppose $f,g$ are one-way-functions, is then $(f+g)(n):=f(n)+g(n)$ a one-way-function or can one construct a counterexample? (The length of $n$ is $\text{ floor}(\frac{\log(n)}{\log(2)})=$ the number of bits to represent $n$)

Comment on answer of @Bulat:
Suppose $f$ is an owf. If (?) there exists a $k \in \mathbb{N}$ such that for all $x \in \mathbb{N_0}$ we have $f(x) \le x^k$. Then as @Bulat mentioned, construct $g(x) = x^k-f(x) \ge 0$. Then $g(x)$ is an owf as $f$ is, but $h(x) = g(x)+f(x) = x^k$ is not an owf. So the question is, if there exists such an $k$.
The argument would also work considering $k^x$ instead of $x^k$. But the same question remains? Why would such an $k$ exist?

Thanks for your help!

The answer is no.

Given $f$ one-way, consider $g(x) = -f(x)$. $g$ is then also one-way, because inverting $g$ would imply inverting $f$.  In particular, supposing $g$ is not one-way, one can invert $f(x)$ simply by negating it and applying the inverter for $g$ (and the success probability is even equal).

In this setting, $h(x) = f(x) - f(x) = 0$ is not one-way as it can be.


Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly? I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map):

positively weighted
undirected
sparse
with about 100 nodes

My current plan is to apply $k$ shortest path routing to each pair; I am now looking for a more efficient alternative (possibly with dynamic programming).

First of all, a crucial difference in computing $k$-shortest paths is if the paths need to be simple or not. A path is called simple, if it does not contain nodes repeatedly. A path with a loop, for example, is not simple. Note that on the Wikipedia page you linked, the articles are concerned with not necessarily simple paths. The case of simple paths seems to be harder than the case with not necessarily simple paths.

The all-pairs $k$-shortest simple paths problem

This seems to be a quite young area of research. A recent paper by Agarwal and Ramachandran can be found on the ArXiv [1]. The previous-work section will also give you some insight into the history of the problem.

The all-pairs $k$-shortest paths problem

Here, indeed, it is the best choice to just repeatedly apply Eppsteins algorithm [2]. The general observation that a repeated application of an algorithm for the single-source version of the problem is the fastest approach was already made in 1977 by E. L. Lawler [3]; Eppstein provides the fastest algorithm to date for this subproblem.

References

[1] Agarwal, U. and Ramachandran, V. Finding $k$ Simple Shortest Paths and Cycles. arXiv:1512.02157 [cs.DS] https://arxiv.org/pdf/1512.02157.pdf

[2] Eppstein, D. Finding the k shortest paths. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, E. L. Comment on a computing the k shortest paths in a graph. Communications of the ACM, 20(8):603–605, 1977.


Loading a word from byte-addressable cache I have asked a similar question at stack-overflow, but then I found this question here, and figured it should go here instead..
So, my question is pretty much the same as the one in the question I linked:
I know that in a byte-addressable cache, a byte-offset (usually the LSB of the address) is used to determine which byte to access out of the designated cache block.
But, if the offset allows the selection of 1 byte out of the block, we would need 4 subsequent accesses to the cache in order to access a single word (assuming a word equals 4 bytes), and I somehow doubt that's the way things execute in real time.. Any clarification regarding that will be appreciated, as I didn't find an answer to that in the previous question).
Thanks in advance :)
Edit:
To clarify my question - I'm trying to understand how can a Byte-Addressable memory output more than 1 Byte at a time.
I'd understand it if the memory Always outputs a whole word, for example, and the byte is then extracted by the CPU according to the requested address by specifying an offset of 0x0 to indicate that it needs 2 bytes - the 1st and 2nd bytes, 0x1 to indicate it needs the 3rd and 4th bytes, 0x00 to indicate it needs only 1 byte - the first byte, 0x01 to extract only the 2nd byte, 0x02 to extract only the 3rd byte, 0x03 to extract only the 4th byte, and specifying no offset at all to tell the CPU "do not extract any specific bytes - process the word as a whole".  That will make for a nice explanation - But I've seen no indication of anything of the sorts while looking at various CPU implementations..

What makes you think that?

If you have a modern high-performance CPU with 256 bit = 32 byte vector registers, then the byte offset determines which group of 1, 2, 4, 8, 16 or 32 consecutive bytes to transfer. Nobody in their right mind would transfer individual bytes. Much too slow.

What will happen and may slow down things a little bit is that if the group of bytes to transfer is not contained in one single cache line, then two accesses are made to two different cache lines. For example, if your cachle lines are 64 bytes and you try to access a 32 bit (four byte) item at byte offset 61, 62 or 63.


Proving a problem is NP Hard Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted value. It's fixed and known beforehand to everyone. So $k$ is NOT an input to this algorithm.
I want to show the problem is NP hard, so this means I have an oracle that tells me whether or not a graph has a cycle whose sum of edge weights equals $k$ for a fixed, known value of $k$.
I thought about reducing from Hamiltonian cycle. So I want to show that I can use this oracle to solve Hamiltonian cycle problems.
Let $G$ be a graph. I want to see if $G$ has a Hamiltonian cycle. I try to construct a new graph to provide to the oracle but I'm not sure how to do so. I think it needs to have $k$ vertices so I tried doing casework on when $G$ has more or less than this many vertices.
I can show that I can solve Hamiltonian cycle problems with $k$ vertices by constructing a new complete graph where edge weights are $1$ if it was in the original graph and a really large nunber otherwise. Then running the oracle on this graph returns true only if there's a Hamiltonian cycle with $k$ vertices. But this doesn't handle the general case. Is this proof fine?
But I'm stuck. Any help is appreciated.

Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$.
Therefore, if $G$ has a hamiltonian cycle, it has a cycle of weight exactly $2$.
Moreover, assume $G$ has a cycle of weight exactly $2$. Such a cycle can either include $v$ or not. If it doesn't include $v$, all its edges will be negative, contradicting a total weight of $2$. If it includes $v$, then it must include two edges of weight $n$, and thus the remaining part of the cycle must be a path, using only edges of weight $-1$, and with total weight equal to $-2n+2$. That meeans such a path must contain $2n-2$ edges, and therefore have $2n-1$ nodes. When connecting said path to-and-from $v$, you have a Hamiltonian cycle.
This means that if you could decide in polynomial time whether $G$ has a cycle of weight $2$ (which is a fixed constant), you could decide whether it has a Hamiltonian cycle in polynomial time.


Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
MAYBE-MST-C(G,w)
  T = empty set
  for each edge e in G, taken in arbitrary order
    T = T U {e}
    if T has a cycle c
      let e' be a maximum-weight edge on c
      T = T - {e'}
  return T

I've found several other solutions (here, here and here) that claim that this procedure succeeds in finding an MST. However, I don't understand any of their proofs.
I can see that this results in a spanning tree. It's spanning because adding every edge e would certainly span G, and removing parts of cycles e' certainly doesn't affect that. It's a tree because any cycle that is added is guaranteed to be immediately removed.
I'm having a hard time seeing why it's minimal (or perhaps it actually isn't?). One of the solutions uses the result of exercise 23.1-5:

if $G$ and has some cycle $c$, then
there exists some MST of G that does not include the edge $e'$ with the
largest weight on that cycle $c$.

While this result superficially resembles the operation performed in MAYBE-MST-C, upon closer inspection, it's not so obvious that it helps, since in the algorithm, T is not guaranteed to span G until the very end, and also the exercise result only claims that an MST exists when omitting one e'; it doesn't say we need to remove all e'. What if the MST that the exercise guarantees requires us to remove the first e', but keep the second? Further, upon removing e', how are we sure that the edges needed to compete the MST have not been removed in previous iterations of the loop?

MAYBE-MST-C does obtain the minimum spanning tree correctly.
Define a "local MST" as a spanning tree for which any cycle resulting from adding some edge $e$ would not have any edges on the cycle with weight $> w(e)$.
Lemma: The tree $T$ generated by MAYBE-MST-C is a local MST.
Proof:
any edge $e$ that is not already in $T$ at the end of the algorithm must have been removed, and thus it must have been a part of some cycle $c$, and was a maximal-weight edge on that cycle at the time $e$ was removed.
Note the rest of $c - {e}$ could have been deformed after $e$ was removed, but each deformation can only replace an edge $f$ with a longer path consisting of weights that are at most $w(f) \leq w(e)$. Hence, if $e$ were added back into $T$ at the very end and completed some cycle $c'$ that had the final result of all those deformations, $e$ is still guaranteed to be a maximal-weight edge on $c'$.
Main result: MAYBE-MST-C results in a minimal spanning tree.
proof: From the lemma, MAYBE-MST-C results in a local MST, and since local MSTs are minimum, the result immediately follows.


Fundamental Boolean Functions I can define any boolean function (I think) using and and not, or using or and not (plus a constant 0 or 1).  And I can define or in terms of xor.  And then there are nor and nand.  So I am wondering:

Why are we traditionally taught boolean logic using and, or and not?
Is there a "simplest" set of boolean functions that can be used to define all the rest?  Or are there "families" of functions that are equivalent in some way?
Do we always need 0, 1 and 2-argument functions (eg 0 or 1 constants, not, and and) to define a family?  Or are there any boolean functions with more than 2 arguments that are fundamental (can appear in an answer to 2)?  Or well-known?  Or common?  If not, what's so special about 0, 1 and 2 arguments?
Is there some underlying mathematical theory (perhaps based on symmetry?) that makes these kinds of questions easier to answer?  For example, how do you rigorously derive all answers to questions 2 or 3?

(I know that a partial answer to 2 (equivalent families) is "yes" because I remember De Morgan's theorem from college, but that's about as far as I can get).

Your main observation is correct - in order to be able to express all Boolean functions, we need not stick to a certain set of connectives. All we need is a complete set of connectives, which is defined by just this property. There are infinitely many such sets of connectives. One such example is given by NOR (or NAND) and the constant $0$ (or $1$). You can probably do with just one ternary connective, but I'll let you figure that out.

Why are we taught AND, OR and NOT? Because these are familiar and useful. It is also common to define propositional logic using the connectives IMPLIES and NOT. It's just a matter of convenience. It is also a matter of convenience that all usual connectives are nullary, unary and binary - already ternary connectives are more awkward to write, functional notation being necessary.

In general, given a set of connectives, you can define the set of all Boolean functions definable from them. Then you can define the concept of equivalent sets of connectives. For example, XOR and NOT is equivalent to XNOR, and $0$ and NOT is equivalent to $1$ and NOT. You can easily prove that two sets $A,B$ of connectives are equivalent if each connective in $A$ can be expressed using connectives in $B$ and vice versa. You can even define an order relation expressing that one set of connectives is at least as expressive as another set of connectives.

One relevant mathematical area is universal algebra. For an application to computer science, you can have a look at Schaefer's theorem and its modern descendants, which form a very active research area. Another connection to computer science is Reckhow's theorem that shows that every formula written using one complete set of connectives can be rewritten using any other set of connectives with only polynomial blowup, and furthermore proofs in any complete propositional proof system can be converted to any other (with a different set of connectives), again with only polynomial blowup.


How to prove that the decidable languages are closed against iteration only by enumerators? We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators?

I try to use induction, but as I understand I wrong...
I'd like to get any help!

I don't really see how to use induction here.

Let's take as an example $L = \{0,1\}$. Then $L^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$. You probably know how to enumerate $L^*$. Same thing works if $L = \{w_0,w_1\}$ for two arbitrary words.

The next step is to handle a language with infinitely many words. Following the earlier convention, I'll just indicate how to solve it for the special in which $L = \mathbb{N}$, and instead of $L^*$ I will use comma-separated sequences. Here is my enumeration:
$$
\epsilon; 1; 2; 1,1; 3; 1,2; 2,1; 1,1,1; 4; \ldots
$$
and so on. See if you can figure out a pattern (or if you don't like my pattern, come up with a different one).


necessary and sufficient pumping lemma - bounded pumping variant There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.

According to that lemma:

A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$, $  x=uvw \cap |v|\ge 1$ such that:

$$\forall i \ge 0,\ \forall z\in \Sigma^*: uvwz\in L \iff uv^iwz\in L.$$

My question to you is: is there any way changing the for all $i \ge 0$ condition to for all $ 0\le i\le N$ for some $N$ - and the lemma will still be correct?

That $N$ may be constant, depend on the lemma's k, and so on.

I can't find an approach to prove it, any ideas?

Yes, what you have observed is correct. We can, in fact, always take $N=0$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once.

A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$ such that $  x=uvw$, $|v|\ge 1$ and $\forall z\in \Sigma^*$,
$$uvwz\in L \iff uwz\in L.$$

As you have observed, the article has basically proved the above fact.

Here is a simpler proof of the "$\Longleftarrow$" direction. Let $[y]$ be the Myhill-Nerode equivalence class represented by string $y$. Suppose $|y|\ge k$.

Let $x$ be the first $k$ symbols of $y$ and $t$ be the rest of $y$, i.e., $y=xt$ and $|x|=k$. By assumption, there exists $u,v,w\in\Sigma^*$ such that $x=uvw$,  $|v|=1$ and
$$yz=x(tz)=uvw(tz)\in L\iff uw(tz)=(uwt)z\in L.$$
The equivalence above means $[y]=[uwt]$. Since $uwt$ is $y$ with $v$ deleted, $|uwt|\lt |y|$. That means the shortest string in a Myhill-Nerode equivalence class must be shorter than $k$.

Since there are finitely many strings that are shorter than $k$ symbols, there are only finitely many Myhill-Nerode equivalence classes. By the celebrated Myhill-Nerode theorem, $L$ is regular.


Superpolynomial time set such that SP=NSP is known? Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer?

UPDATE: It must be defined by time and strictly between $\mathsf{P}$ and $\mathsf{EXPTIME}$. I was wondering, what if Cobham's thesis is wrong and we are fighting with $\mathsf{P=NP}$ because of that thesis when the really useful question is another one? Maybe one that's even already answered?

Take any time complexity class and its corresponding nondeterministic counterpart: $\mathsf{DTime(F)}$ and $\mathsf{NTime}(F)$ where $F$ is a family of nice functions containing polynomials and bounded by exponential functions. You are asking if we know these two classes are equal. We don't know!

Take $SAT$ as an example. A certificate can be verified in linear time so it is in $\mathsf{NTime}(n)$. However there is no algorithm that solves even very simple instances of $SAT$ (e.g. decide if the propositional statement that n+1 pigeons can be mapped into n holes is false) significantly faster than brute-force, i.e. exponential time. In other words, we don't even know if $\mathsf{NTime}(n) \subseteq \mathsf{DTime}(f)$ where $f$ is a little bit smaller than exponential function $2^n$. IF what you are asking was true then the lhs would be subset of your $\mathsf{NTime}(F)$ and therefore by your assumption a subset of $\mathsf{DTime}(F)$ where $F$ is smaller than exponential functions.

The question about $\mathsf{P}$ and $\mathsf{NP}$ is not only important because of Cobham's thesis that efficient computations are captured by $\mathsf{P}$, we don't know any simulation of nondeterminisitic time bounded machines by deterministic ones which doesn't use brute force search for the certificate. So the essential question about $\mathsf{P}$ vs. $\mathsf{NP}$ is can we find a certificate in a space exponentially faster than brute-force search of the space?

In fact, the question was known in Russian literature as the perebor problem (the brute-force search problem).

If you don't accept Cobham's thesis then you can think of $\mathsf{P}$ vs. $\mathsf{NP}$ question as the flagship of questions about the relation between verifying and constructing answers, or as I said above, as the question about existence of deterministic search algorithms which are exponentially faster than brute-force search.


Probability of arising of simple graph in configuration model I am studying a configuration model building $d$-regular graphs and reading the following article:
The expansion of random regular graphs by David Ellis.
I am stuck on the following step:

Each simple labelled $d$-regular graph on $n$ vertices has the same probability of arising. Indeed, it is easy to see that a simple d-regular graph on $[n]$ arises from precisely $(d!)^n$ of the matchings.

Where does this $(d!)^n$ come from?

Consider a simple $d$-regular graph. For each vertex, assign numbers from $1$ to $d$ to the edges adjacent to it. There are $(d!)^n$ ways to do so. Each such assignment corresponds to a particular perfect matching in the configuration model, and vice versa.


pseudo clique with at least connectivity x and maximum weight of the nodes Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum_{n \in N}w(n)$.   The connectivity of the graph is defined to be $c(G) = \#E_G / (\#N_G \cdot (\#N_G - 1)/2)$ -- this measures the fraction of edges in comparison to the maximum possible number of edges.

Given $G$ and a number $x$, I want to find the maximal-weight subgraph $G'$ which has at least connectivity $x$, i.e., I want to find $G'$ that makes $w(G')$ as large as possible, subject to the requirement that $G'$ is a subgraph of $G$ and $c(G') \ge x$.  This looks like some kind of generalization of the clique problem; here I essentially want to find a "pseudo-clique".  Is there any efficient algorithm for this problem?

Your problem is NP hard, because with $x=1$ (real clique) and the same weight for each node you get the  maximum clique problem, which is NP complete. You can try to find a reduction in order to use a SAT solver, or just enumerate the $2^N$ subgraphs.

Furthermore, unless P = NP, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $O(n^{1 − \varepsilon})$, for any $\varepsilon > 0$. Wikipédia

We can't even find a good probabilistic algorithm, unless NP is in BPP.

If your $x$ is fixed and $<1$, look at the following article:

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem.  Takeaki Uno.  Algorithmica, January 2010, Volume 56, Issue 1, pp 3-16.

It considers a variant of the problem with no weights, but you can substitute each vertex by a clique of size square root of its weight, if the weights are not too big, and then apply their techniques.


What does up arrow ($\uparrow$) mean in pseudocode? I'm learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993, SIAM, pages 311–321; PDF).  The following pseudocode appears in Algorithm 1.

$$\begin{align*}
\hspace{2em}&\hspace{-2em}
\textbf{function}\text{ Make_vp_tree(}S\text{)}\\
&\textbf{if }S=\emptyset\textbf{ then return }\emptyset\\
&\text{new(node);}\\
&\text{node}\!\uparrow\!\!\text{.p} := \text{Select_vp(}S\text{);}\\
&\text{node}\!\uparrow\!\!\text{.mu} := \text{Median}_{s\in S}\, d(p,s);\\
&\dotsc
\end{align*}$$

node is a node of vp-tree, so I know what node.p means, but what do that up arrow means in this context?

The algorithms in the paper you link to are described in a notation quite similar to Pascal, a language that treats pointers in a very particular way. In Pascal, pointers are declared as references to values of specific types (a pointer to an integer can never refer to a boolean, for instance).

The upward arrow, in the example you reproduce, is a dereferencing operator. Clearly, node is a pointer to a value of a record type (not a record itself), of which p and mu are fields, so node.p has no meaning.

Check out this similar question for further clarification.


Improvement Heuristics for Asymmetric TSP i have been solving the Time-Dependent Traveling Salesman Problem using
an Ant Colony Optimization.
Upon reading the ACO papers, there are several reminders which state
that ACO performs best with daemon actions - improvement heuristics.

In the classical TSP, the most common improvement heuristic used is the k-opt exchange,
which works particularly well because one does not need to calculate the whole
solution cost, but only differentials on the updated solution.

When the problem is assymetric (which is the case for the time-dependent variation), this is not the case.

I wonder if there are usefull improvement heuristics which can be used as daemon actions to the Assymetric/time-dependent TSP.

I already did some research on this subject, but found no interesting material.

I have the exact same doubt now, so, I found your question because I did a heavy research about this theme and didn't find any good direction yet.
As you, I'm currently working on TSP and VRP variations and solving it by the Ant's Colony Optimization Method.

I have an instance of 16 cities to be visited, one origin and one destination, I optimized it using pure ant's algorithms and the best result I got was 557 km, by comparation the nearest neighboor algorithm found 586 km as a result, however, I notice that the ant's algorithms aren't precise, sometimes it returns a very bad result, better than the nearest neighboor though. But I wasn't satified with this drawback, and I started to read about heuristics (daemons actions) to be coupled with the ant's algorithms, then It is very interesting that all of them assume that we are working with a symmetric matrix, but real problems are hardly symmetric.

I first tried to apply the 2-opt heuristic, because I read that it is fast and give a good result, so it suits for a real application that an user waits to get the answer as fast as possible and as good as possible. But latter I saw that the step of 2-opt which reverses a path when exchange edges is guaranteed only when working with symmetric matrices...

Well, After all, I applied a very simple heuristic, that I don't know the name yet, but I saw some comments that it is not a good solution (because doesn't solve the crossed arcs problem and may create more of them), even though, it helps me to provide better solutions and also more precise, as an example, the instance I told about above, it gives the result of 554 km almost all the time.

The heuristic I applied does this job:
After the ACO build a solution, I refine it by exchange cities (in other words, exchange vertex or nodes), if it improves the solution, I save this new solution and continue the process of exchanging cities, using the new solution constructed until I reach the solution's vector length.

For example, if I have the following path as a solution given by the ACO:

A -> B -> C -> D -> E -> F

the heuristic moves B ahead in the path, for example:

A - > C -> B...

then:

A -> D -> C -> B -> E -> F

if it finds a better solution, for example, let's suppose the above solution is an improvement, then it continues moving the city in the second position in the solution vector:

A - > E -> C -> B-> D-> F

Then, it starts the same procedure to the third position city...

I'd like to add that the solution which updates the pheromone matrix is the solution built by the ACO and improved by this heuristic.

As I experienced, the ACO does a pretty good job creating solutions with very few crossed arcs, because this the heuristic applied is working fine, and as we are working with asymmetric matrix I think that it is possible to crossed arcs being better paths than paths without any crossed arc... But It is just my feeling, actually, I analyzed the solutions above only by the value of route's length in kilometer, but I did not plot them yet to see how they look like.

Well, I hope to help you with these informations, and if you have find any nice heuristic to couple with the ACO as a daemon action, keep me posted!


How to find a nearly-optimal covering of a set using SAT? I have recently started thinking about application of SAT in solving different problems and how I can encode those problems into a SAT problem.

I think one of the interesting problems where SAT solvers can be used is finding a minimal representation for a logic expression. However, I have trouble encoding the problem into a SAT problem.

In very old representations of an n-input logic circuit, three sets F, R, and D are defined. F represents the ON-set, which corresponds to permutations of input that cause a one in the output. R is the OFF-set, which corresponds to permutations of input that cause a zero in the output. Finally, D is the DON'T CARE-set which corresponds to permutations of input where output is not specified (could be set to either one or zero during optimization).

The objective is to find a minimal conjunctive normal form (CNF) that has the minimum number of clauses and each clause has the minimum number of literals. This CNF should cover all elements of F and may potentially cover some elements of D, but should not cover any elements of R.

For example, assume that a 3-input function is defined in the following way:

A B C | Y
---------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | -
1 0 1 | -
1 1 0 | -
1 1 1 | -

where A, B, and C are inputs, Y is the output, and a - determines a don't care output.

In this problem, a minimal CNF that meets the objective is O = B, because whenever B is true, the output is either true or don't care, but never false. Without having the DON'T CARE-set, a minimal representation would be O = ~A B, but DON'T CARE-set has allowed a more compact representation.

Is there a method to encode this problem as a SAT problem where inputs are F and R?

This problem is known as circuit minimization.  It falls within the broad area of logic synthesis.

The problem is known to be $\Sigma_2^P$-complete.  As a result, it is unlikely to be in NP (contrary to what you wrote).  And that means that it is unlikely to be solvable in polynomial time with queries to a SAT solver.  (NP is basically the class of problems you can solve with a SAT solver in a single query; $P^{NP}$ is the class of problems you can solve with an unlimited number of queries to a SAT solver; and $\Sigma_2^P$ is conjectured to be larger still, so a $\Sigma_2^P$-complete problem is conjectured not to be in NP or $P^{NP}$.)  There may still be heuristics that use a SAT solver along the way, but these heuristics either might make mistakes, might fail for some inputs, or might take exponentially long in some cases.

Anyway, there is a lot of literature on circuit minimization.  As far as I know, one standard approach is to use techniques built on Quine-McClusky, Espresso, etc.

You might be interested in approaches based on interpolation.  I believe those approaches use a SAT solver as a building block.


How to keep track of changes done to concurrent stacks? I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:

add-int(a: int, b: int): a b +
add-float(a: float, b: float): a b +

and I have two stacks with the following:

Int [1 2 3]
Float [4.0 5.5]

I can just do:

add-int add-float

and the new stacks will be:

Int [1 5]
Float [9.5]

Everything works well there, but if I were to add parametric polymorphism with this function:

add-num(a: num, b: num): a b +

Then it would not work as one would expect. Is it going to add the two integers or the two floats? or perhaps one from each?

To solve the issue, I added a new stack Num that keeps the address of every number pushed into the other stacks to keep a sense of history, but it created two new issues.

First, memory addresses take a lot of space, sometimes more than the data itself, and this would only get worse if I were to add new number types like ratios and complex.

Second, what if I wanted to pop a number that is on top of the stack for its type but way behind in the Num stack.

For example:

> 1 2 3.14 4.0 5/5  -- This is the expression.
Int [1 2]  -- These are the stacks.
Float [3.14 4.0]
Ratio [5/5]
Num [&Int[0] &Int[1] &Float[0] &Float[1] &Ratio[0]]

> add-int  -- Then I do this.

If I call the function above, there is no issue popping the two integers, but what about deleting the two pointers in the Num stack? It can get pretty expensive to look for the element and remove it every single time a number is popped.

I have realized that this approach is not pretty effective in terms of space consumption and performance, so is there an alternative, more efficient way of keeping track of the changes done to these stacks?

I would use doubly-linked lists instead of opaque stacks for this.

Node = {
    type : "INT" or "FLOAT"
    value : int or float
    prev-generic : pointer to Node
    next-generic : pointer to Node
    prev-specific : pointer to Node
    next-specific : pointer to Node
}

Now you can keep three lists: a list of ints (using the specific pointers), a list of floats (using the specific pointers), and a list of both (using the generic pointers). If you keep track of the head of each list, you can treat them as stacks (pushing and popping in $O(1)$), and a popped node can also be deleted from both stacks in $O(1)$ just like in a normal doubly-linked list.


In Lbest PSO, how is the local best position in a neighbourhood defined? I am implementing a couple of PSO (particle swarm optimization) algorithms, and I got stuck on a bit of detail which I could not clearly determine from the papers I have read. In lbest PSO, for each particle, the velocity update step takes the best particle's position in that particle's neighbourhood into account. What I am not 100% clear on is how that "best particle" is defined. To my understanding, it could be

(a) the best current position of each particle in the neighbourhood,

(b) the best pbest position (in memory) of each particle in the neighbourhood, or

(c) the best lbest psoition of each such particle, which could be initially determined from (a) or (b) as above, but over time allow information about other neighbourhoods' best positions to distribute across the swarm.

I realize that each of the above may be a valid and published version of PSO. I just want to know which version is usually referred to as "lbest PSO".

In general option b) is how a Lbest PSO is implemented.

This makes sense, as the Lbest particle is meant to be the social influence, and from an optimization perspective you would utilize the best candidate solution information from you neighborhood, which would inherently be the best of the pbest positions.


Which algorithm can I use to allocate human resources? I have to manage shifts of a variable number of people inside several rooms for a week.
Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same for everyone.
Every person could ask for specific shifts and this could be accepted if a suitable solution can be found.
I could have other constraints, but let's face this very basic situation.

Now the questions:

Which algorithm should I study and use?
Is there some free library I can use for this purpose?
Is there something I can use for C#?

Since Vince asked me to publish my solution, I decided to write this long post.
Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test.
Credits for Hungarian algorithm code must be done to vivet.

PURPOSE

I need to create shifts for M workers (variable number each week) on N slots (usually 50 each week, but sometimes some slot could be unavailable).
Each worker can suggest slots he wants to take and others he can't absolutely take and, if possible, these requests should be taken in account.

GENERAL IDEA

Given that creating costs matrix for Hungarian solver can be a pain, I decided (just a quick solution) I can create text files for each worker to report his request and one file for unavailable slots.
All these files must be in the same folder.

FILES STRUCTURE

A single text file must have as many rows as daily slots (usually 10) and as many columns as working days (usually 5).
Each cell must contain a preconfigured char:

O means worker really needs that slot assigned
o means worker would like to have the slot assigned
- means no preference on that slot (it's the default naturally)
x means worker would like not to have the slot assigned
X means worker can't work on that particular slot

A sample could be

X x - - O
X x - - O
- - - - O
- - - - -
- - - - -
- - - o -
- - - o -
- - - - -
- - - - -
x x x x x

Unavailable slots file must have a well defined name (always the same) and its content will have the same structure of workers files. Naturally each cell having a value different than - means that slot is not available to workers.

CODE

Source code can be found here.
Unfortunately .NET Fiddle uses framework 4.5, so program can't be compiled and run online due to the fact I use a newer framework (4.7.1).
Also consider my real code is organized into several files!

It works and it's fast, so I'm completely satisfied with this part.

A STEP FURTHER

First problem solved, pretty good. But now I have to face the next one: I have several locations to assign workers shifts to and these locations share the same working hours.
A first attempt was to raise the number of columns on each file: cols 1-10 are for the 1st venue, cols 11-20 for the 2nd and so on.
Code works without any change and Hungarian algorithm processes data in a while, good; but, as expected, I end having overlapping shifts for the same workers on multiple venues (it's random, but always happens).
I could solve this problem by computing 1st venue, then changing each worker requests denying slots already given in the 1st venue before computing the 2nd one; not exactly the best way I'm sure, just an idea I had, and I'm not sure I can always find a solution.

OTHER OPTIMIZATIONS

I could also think about adding other rules (e.g. if possible worker should have max 2 ranges in a day (avoiding for example solutions having slots 0, 2, 4, 6 and 8 and preferring slots 0-2, 6-8 instead) and limits, but this goes too far from the starting question, so it will be something I'm asking in future and I'm quite sure it could need some more complex algorithm or libraries (e.g. ORTools by Google) I'm searching/studying.


Coin Change Problem Recurrence Relation with one parameter I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not depending on the set $ S_{m} $? What would this function look like in general? If a concrete example is needed what would it look like for the set of coins {3 cents coin, 4 cents coin, 5 cent coin}?

One possible definition is
$$
C(N) = \sum_{i \in S_m} C(N-i),
$$
with base cases $C(0) = 1$ and $C(x) = 0$ for negative $x$. This counts the number of ways to write $N$ as a sum of elements of $S_m$ where order matters, that is, if $a \neq b$ then $a + b$ is different from $b + a$. As an example, if $S_m = \{1,2\}$ then $C(3) = 3$ since $3 = 1 + 1 + 1 = 1 + 2 = 2 + 1$.

It is, however, possible to obtain a one-parameter recurrence relation, using inclusion exclusion:
$$
C(N) = \sum_{\emptyset \neq A \subseteq S_m} (-1)^{|A|+1} C(N-\Sigma A),
$$
where $\Sigma A$ is the sum of elements in $A$. For example, if $S_m = \{3,4,5\}$, then the recurrence is
$$
C(N) = C(N-3)+C(N-4)+C(N-5)-C(N-7)-C(N-8)-C(N-9)+C(N-12).
$$
The initial values are
$$
C(0) = 1, C(1) = C(2) = 0, C(3) = \cdots = C(7) = 1, C(8) = \cdots = C(11) = 2,
$$
or in table format:
$$
\begin{array}{c|ccccccccccc}
N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline
C(N) & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2
\end{array}
$$


Can only information(data) be stored in ram? Basic question, but is only information/ data stored in ram? Are computer files such as a word file considered information/ data? This is one of the questions in a summer assignment for ap computer science.

RAM is just a really fast hard disk (except the contents are usually lost if powered down). It can store anything you could store on a hard disk (programs, documents, pictures, temporary data,...).


Can/Do multiple processes run simultaneously on a multi-core system? I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run simultaneously in a multi-core system. However, can multiple processes run simultaneously in such a system as well?

In other words, in a dual core processor:
 - How many processes can run simultaneously(without context switching) if all processes are single threaded?
 - How many processes can run simultaneously if there are 2 processes and both are multi-threaded?

This question is more related to the difference between a thread and a process. Here is a hint: When it comes to kernel scheduling structures, the only thing the kernel looks at is threads, not processes.

A process is easier to understand as a group of threads. All processes have to have at least one thread, and it is that thread that is scheduled in the operating system, not the process.

So, with this understanding, in a dual core system with two processes each containing a thread each, there are two threads total that are scheduled on the two cores.


How to Prove E $\subsetneq$ EXP? I want to prove that $E \subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem

I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof:

$E\subseteq TIME(2^{cn})$
$TIME(2^{cn}) \subsetneq TIME(n^2 \cdot (2^{cn})^2)$ Time Hierarchy Theorem
$E \subsetneq EXP$

Is this correct ?

I have done something similar with $P\subsetneq EXP$:  PROOF IDEA:

$P\subseteq TIME(2^n)$
$TIME(2^n)\subsetneq TIME(n^2\cdot (2^n)^2) \ \text{Time Hierarchy Theorem}$
$TIME(n^2\cdot (2^n)^2)\subseteq EXP$
$P\subsetneq EXP$

  Complexity class E: $E=\bigcup_{c\ge 0}TIME(2^{cn})$
  Complexity Class EXPTIME: $EXP=\bigcup_{c\ge 0}TIME(2^{n^c})$
  Time Hierarchy Theorem: $TIME(f(n)) \subsetneq TIME(n²\cdot (fn)²)$

The Time Hierarchy Theorem shows that allowing Turing Machines more computation time strictly increases the class of languages that they can decide. Recall that a function $f : N → N$ is a time-constructible function if there is a Turing machine that, given the input $1^n$ , writes down $1^{f(n)}$ on its
tape in $O(f (n))$ time.

The time hierarchy theorem states that if $f(n)$ is a reasonable function (technically, time-constructible), then there are some languages computable in time $f(n)$ that require (almost) time $f(n)$. More accurately, for any $g(n)$ satisfying $$ \frac{g(n)\log f(n)}{f(n)} \longrightarrow 0, $$
there is a function computable in time $f(n)$ but not in time $g(n)$.

Intuitively, this is saying that if we have more time ($f(n)$ rather than $g(n)$), then we can compute more languages. The theorem is a time-bounded version of the undecidability of the halting problem, and is proved in a very similar way.

In your case, you want to show that time $O(2^{n^\gamma})$ is more powerful than time $O(2^{cn})$. Here is one naive attempt: pick some $f(n) \in O(2^{n^\gamma})$ such that for all $g(n) \in O(2^{cn})$, the prerequisites of the time hierarchy theorem are satisfied. This shows that for each particular $c$, there is a language in EXP not computable in time $O(2^{cn})$. However, for all we know it can be computed in time $O(2^{(c+1)n})$, and so this doesn't show that EXP is larger than E.

Instead, you want to find a single language in EXP which is simultaneously not computable in time $O(2^{cn})$ for all $c$. To ensure that, you need to pick $g(n)$ judiciously, and I'll leave you to that.


Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard? Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete?

This would be where the goal is to group a multiset whose size is evenly divisible by 3 into triplets that sum to as close to a target as possible and to produce this grouping. This would not be a decision problem but an actual optimization problem.

The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise.

Two examples of such functions are the maximum and the sum of the absolute differences between the sum of the elements in each group and the target.

Under this assumptions, the above optimization problem is strongly NP-hard since the answer to the decision problem is "yes" if and only if an optimal solution $S$ to the optimization problem satisfies $f(S)=0$.

It would not be NP-complete since it does not belong to NP (which only contains decision problems).


The "complexity" of the Turing machine state specification Suppose we want to represent some arbitrary Boolean function $f(x_1,x_2,...,x_N)$ on $N$ bits. We can explicitly specify such a representation using the disjunctive normal form. For "most" Boolean functions, this representation will be of length exponential in $N$, and incompressible (as per Shannon). We will assume we have chosen such an incompressible function.

We can build a Turing machine corresponding to this circuit, which ACCEPTs an input $\mathbf{x}$ if and only if $f(\mathbf{x}) = 1$. We can then ask what complexity such a Turing machine would have.

Now, the subtlety is: since our function is incompressible, any attempt to physically represent it must, naively, be "exponentially large"... in some sense. But we can "hide" the "exponentialness" of this in various places based on how we define our Turing machine, which would appear to change its computational complexity.

How does complexity theory handle this case?

Now, if we were treating the DNF as part of the input, we could create a Turing machine and feed our DNF and some bitvector to evaluate as an "exponential-length" input. We would then know that our Turing machine would take time $O(2^N)$ just to read the DNF, so accounting for everything relative to $N$, we're in (at least) exponential time.

But, as we are "building the circuit into" the specification of the Turing machine itself, we can recognize this language in $O(N)$:

Check if the first bit is 0 or 1. Then, we have a branch to two states corresponding to $f(0,x_2,...,x_N)$ and $f(1,x_2,...,x_N)$, and transition according to the input.
Repeat with the second bit. For each possibility, we have two more states, yielding four states total: $f(0,0,...,x_N)$, $f(0,1,...,x_N)$, $f(1,0,...,x_N)$, and $f(1,1,...,x_N)$.
Continue branching until the end, and then ACCEPT/REJECT according to the specification of our function.

Of course, our Turing machine is "pathological" in that it now requires an exponential number of states. But, technically, since time complexity does not take this into account, it looks like we've gone from $O(2^N)$ to $O(N)$.

We can "fix" this to obtain a Turing machine with only one nontrivial state that recognizes the language in $O(1)$! Simply change the alphabet to be of size $2^N$, so that bitvector is viewed "atomically" as a single entry in the alphabet. Then we encode membership in our Boolean function by a single state transition to ACCEPT or REJECT based on the input. Of course, now the problem is that our "$O(1)$ machine with one state" has an exponentially large state transition table.

My question: What is the complexity of our language, expressed relative to $N$? Naively, I would like to say it's in EXPTIME, since the "exponential speedups" given by the last two Turing machines are clearly pathological, but I don't normally see this metric accounted for anywhere in complexity theory.

In general, how does complexity theory handle this? Are such pathological machines explicitly excluded in the main results of the field, and if so, what criterion do we use for excluding them?

Complexity theory typically handles asymptotics, not finite cases.  In particular, complexity theory looks at the asymptotic running time as a function of $N$.  If you have only a single fixed $N$, then the standard framework doesn't apply.  It's not possible to talk about the running time being asymptotically an exponential function of $N$, because with only a single value of $N$, it is just a fixed constant; it's not a function of anything.  Complexity classes like EXPTIME are defined in terms of these asymptotics, so they aren't applicable if you have just a single function you want to compute, for a single fixed value of $N$.

So, if you want to apply the machine of complexity theory, you need to consider a family of boolean functions, one for each $N$, and a single Turing machine that computes all of them.  Then you can characterize the running time of that Turing machine as a function of $N$ (the length of the input).  At that point, there is no opportunity to "hide exponentialness" in the definition of the Turing machine, because you need to pick a single fixed Turing machine that computes all of them, and your idea for "smuggling exponentialness" can't be done if you have a fixed Turing machine.  Whatever you do, you only get a constant-factor speedup.

I have seen some formalizations that characterize the complexity not by the running time of the machine, but by the running time plus the length of the machine specification.  For instance, in the RAM model, you can use the running time of the algorithm plus the length of the code of the program.  Then, you can measure how this behaves as a function of $N$.  You can even characterize it for a single $N$, but then you're not dealing with asymptotics or complexity theory or complexity classes like EXPTIME; you're just saying that the least-complexity program to implement this one function has time+size equal to such-and-such.  For instance, this approach is sometimes used in theoretical cryptography (called "concrete security"), where we care about a single value of $N$, rather than the asymptotic behavior as $N \to \infty$.  But again, then you can't talk about complexity classes like P or EXPTIME.


Is the following true? log2(2n) ∈ O(log2(n))? Is $\log_2(2n) \in O(\log_2(n))$ ?

I don't know how to prove whether this is true or false.
Any help is appreciated

We have:
$$\log_2(2n) = \log_2(2) + \log_2(n) = 1 + \log_2(n) < 2 \times \log_2(n)$$

You can take $c = 2$ and as $\log_2(2n) < c \times \log_2(n)$ for $n > 2$, we can say $\log_2(2n) \in O(\log_2(n))$.


Prove completeness of a language with Turing Machine I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling a Turing Machine with this language. Like Turing Machine has completeness, the fact to simulate it shows the language has completeness too.

So, to prepare this, I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine.
If I do a similar program in my computer language, is that enough to prove the completeness of this latter?

I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine

This is not enough. You still need to prove, that your class can simulate ANY Turing machine.

Normally to show Turing completness one will

Implement Universal Turing Machine in this language and
Show how unlimited tape is possible.

Of course unlimited tape is impossible in realistic hardware, but even for idealized translation model for languages like C, there are problems

Also I want to add one more clause: make sure that your language well-defined enough. It shall either have mathematical definition or clear formal translation model in language standard.


Minimum number of processes for the deadlock? A system has 6 identical resources and $N$ processes competing for
them. Each process can request at most two requests. Which one of the
following values of $N$ could lead to a deadlock?

1
2
3
4

My attempt:
Deadlock free condition is:
$R  \geq P(N-1)+1 ,$
Where R is total number of resources,
P is the number of processes, and
N is the max need of resources by each process.
$6 \geq P(2-1) + 1$
$6 \geq P + 1$
$5 \geq P$
So, the number of processes should be less than $5$ for the deadlock free condition.
Hence, all options can not be deadlocked.

In this exercise problem the answer given option (4).

Can you explain it in a formal way, please?

I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time.

So any deadlock must have at least four participating processes.  To participate in a deadlock, a process must hold at least one resource. Further, a process cannot hold more than two resources so a process that currently has two resources can definitely run until it frees at least one of those resources. Therefore, if there is a deadlock, it must involve four processes, each holding exactly one resource. This means that there are two resources free so any process that requests a resource will be granted it and will then run until it releases one or both of the resources it holds. Out of our set of four supposedly deadlocked processes, at least one is always runnable, so there is no deadlock. (In fact, at least two are runnable at all times.)

Perhaps the question-setter had the following situation in mind. Suppose processes 1 and 2 are using two resources each and processes 3 and 4 are using one resource each. Now, if 3 and 4 each request one more resource, they will block. But this is not deadlock because the situation can be resolved by either one of the two runnable processes (1 and 2) giving up one of their resources. Deadlock is the situation where every one of a set of processes is blocked and the only way to resolve the situation is for one of those blocked processes to give up resources, which it can't do because it's blocked.


Reduce subset sum to 3SAT How to do it?
I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction

The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods.

For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-bit result.  Convert the routine to a circuit, then convert the circuit to CNF.  Then add simple declarative CNF clauses that force the $2n$ output variables of the circuit to match the bits of the integer that you want to factor.  The resulting CNF instance will be satisfiable only if a bit pattern for the two $n$-bit numbers exists that when multiplied together produces the 2$n$-bit number you want factored.  (If you want trivial solutions excluded then you also need to add two extra CNF clauses that demand the most significant $n$-1 bits of each multiplier are not all zero.)

Subset sum is a bit more intricate.  You need to write $n$ routines, each of which returns a particular one of the $n$ integers of the problem set or zero depending on the setting of a parameter bit.  These routines feed input into another routine you wrote that sums all $n$ of its inputs and outputs the result.  Convert all this into a circuit whose inputs are the parameter bits and whose outputs are the result of the addition routine.  Convert the circuit to CNF.  Add declarative CNF clauses that force the output variables of the adder routine to match the bits of $k$, the number a solution must sum to.  The resulting CNF instance will be satisfiable only if there exists a bit pattern of the parameter bits selecting a subset of the problem set that sums up to $k$.


Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array? Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ elements of $A$ in $O(n^2)$ or $O(n^3)$ time complexity? If yes what would be the pseudocode?

This seems to be a knapsack problem to me and according to Wikipedia it's an NP-complete problem. So even if the array was unsorted in the first place and we wanted to sort it it would take $O(n\log n)$ time which doesn't really help if the problem is NP-complete anyway. Yet I wonder if some optimization may be made to achieve better time.

Please treat $x$ and $k$ as constants, for running time analysis.

It depends on the numbers in the array. For example if all array elements are positive integers, and the requested sum is S, then O(nS) is easy.


Loading a word from a byte addressed cache In a cache with byte addressing, the byte you want to load is selected using the block offset. But what if I execute a LW instruction and don't want a single byte but a full 32 bit word?

Is there some logic that selects whether you don't look at the block offset and just load the whole word (when you use a "load word" instruction) or you look at the block offset to choose the right byte (when you use a "load byte" instruction)?

For nearly all major architectures, a cache line is 64 bytes wide. All memory transactions from your L1 cache all the way out to DRAM will use 64 byte lines. The only place where the byte address-ability comes into play is between the processor core and the L1 cache. It is common for L1 RAMs to be built with byte enables or some from of specification to a subset of the bytes from a 64 byte cache line.

Let's assume the interface from the processor to the L1 cache yields an address and a width (number of bytes). Suppose you want address 0xF002 and you want 4 bytes. The cache line is address 0xF000 (0xF002 & ~0x003f), the offset within the cache line is 0x0002 (0xF002 & 0x003f), and because you specified a 4 byte width you'd receive bytes 0xF002, 0xF003, 0xF004, and 0xF005.

Most processor/cache interfaces will only support common widths (1, 2, 4, 8 bytes), and basic architectures will force the addresses to be aligned (i.e., a 2 byte read can't start at an odd address). More advanced architectures will handle the misalignment in hardware (see MIPS unaligned load/store for a bad implementation). x86 allows unaligned loads and stores. Here is a short list of reasons unaligned memory accesses are bad:

  Why unaligned access is bad

  The effects of performing an unaligned memory access vary from
  architecture to architecture. It would be easy to write a whole
  document on the differences here; a summary of the common scenarios is
  presented below:

  Some architectures are able to perform unaligned memory accesses    transparently, but there is usually a significant performance cost.
  Some architectures raise processor exceptions when unaligned accesses    happen. The exception handler is able to correct the
  unaligned access,    at significant cost to performance.
  Some architectures raise processor exceptions when unaligned accesses    happen, but the exceptions do not contain enough
  information for the    unaligned access to be corrected.
  Some architectures are not capable of unaligned memory access, but will    silently perform a different memory access to the one that was
  requested,    resulting in a subtle code bug that is hard to detect!

  It should be obvious from the above that if your code causes unaligned
  memory accesses to happen, your code will not work correctly on
  certain platforms and will cause performance problems on others.
  from: https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt


symmetrical subtraction between $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NPC}$ If $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NP-Complete}$ and $L_3$ is the symmetric difference between $L_1$ and $L_2$, is $L_3$ also in $\mathsf{NP-Complete}$ necessarily?

I'm pretty sure the answer is no but I can't find even one example that shows I'm right.

The answer is actually yes. Some intuition is that, when considering $\mathsf{NP}$-completeness (or in general, considering any complexity class under polynomial-time reductions), polynomial-time parts of the computation don't matter. Since $L_1$ is polynomial time, and $L_1 \Delta L_2$ and $L_2$ can be computed from each other knowing the answer to $L_1$, they should both be equivalent languages, up to polynomial-time computations.

Formally, to show "equivalence" we use polynomial time reductions. So you could solve this problem by:

Finding a polynomial-time reduction from $L_2$ to $L_1 \Delta L_2$. (How do we compute $L_1 \Delta L_2$ from $L_2$?)
Finding a polynomial-time reduction from $L_1 \Delta L_2$ to $L_2$. Hint: use the fact that
$$(L_1 \Delta L_2) \Delta L_1 = L_2$$

Once you have done this, you have shown that $L_2$ and $L_1 \Delta L_2$ are equivalent; if you are familiar with the notation,
$$
L_2 \le_p L_1 \Delta L_2 \le_p L_2
$$
which  means if one of them is $\mathsf{NP}$-complete, then both of them are.


How do you proceed if your milp is not solvable We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).

We went with a very simple aproach (make a cube person x visit x Time and add constraints from here on). Our solution works well if the problem is solvable.

Our customer needs a solution with alternative options if the problem is not solvable, for example "here is a possible solution with X more people" or "a solution with 2 hours more worktime".

Our initial thoughts were to extend our people / time cube by a given number of cells and then add high penalty values to our goal function for these values.

Does anyone have a better idea / knows what is common practice?

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following:

Precision

Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html

You can use this in two ways:

Sanity tests

If you don't know if your problem is solvable in practice, i.e., constraints are not contradictory in a non-obvious way, just set the precision to lowest possible value and try to solve the problem. The solver should just find anything meeting the constraints practically ignoring the cost function.

Next, when you know that the problem is solvable, you can tighten the constraints. In your example you mention the number of people, first you can start with $x+10$ and if it works you then decrease it to $x+5$ and so on. By doing so you can easily estimate which set of parameters and constraints you can further optimize.

Practical precision

The question is whether you need the highest possible precision or maybe you can bend the rules and consider using less "optimal" solution. This can highly speed up the calculations, i.e., in my problems I was able to find the solution in seconds instead of hours by switching gap from $0.0001$ to $0.01$ in Gurobi.

Hard constraints and soft constraints

Common approach is to change some of the constraints to constraints with penalty. For instance, instead of saying that $x < 10$ you say that $x - p < 10$ where $p \ge 0$. Next, you add $p$ to your cost function with big negative multiplier. Such a variable splitting can help finding solutions in case of infeasibility, what's more, if you report the solutions during calculations you can use them to get better approximations of the constraints you can drop to get better results. It looks like this is something you already considered and this is a common approach.

Presolve

Depending on the type of your problem, you may be able to divide it into multiple phases and calculate the solutions in parallel. Using this method with "sanity tests" method mentioned above you can still have some solution in case when your most wanted model is not feasible.

Example: if you are optimizing for two "realms" (like number of people and number of tasks), try to set some value manually and optimize the other value for that case. By doing this you make the model much easier so you can calculate multiple of them.

Simplify the model

It sounds easy but in fact can be very hard. Make sure that you don't perform unnecessary difficult operations (like calculating GCD or multiplying variables). Look for easier formulations including constraints moved to cost function (i.e, instead of calculating the minimum of a set and them maximizing it with the cost function, use min-max trick). Make sure that you have smallest possible domains (especially for so-called "big $M$" variables). Also, check your floating point precision.

Just deal with it

Sometimes you just can't mitigate it, after all it might not be solvable in any acceptable time. You can consider calculating different problem (i.e., completely different approach) or use different algorithm at all (neural nets, simulated annealing etc).


How long will selection sort and merge sort take to sort a certain number of items? I am dealing with a sample exam question that I cannot understand which is as follows:

  Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate the amount of time it would take to sort 100,000 items. If Mergesort took 1 second for 100 items and 15 seconds for 1000 items, how long would you expect it to take for 1,000,000?

Now, I know that selection sort has worst-case upper bound of $O(n^2)$. So as size of input $n$ increases, $f(n)$ increases in a quadratic manner. So I understand the concept of it but I don't understand how to use it to solve for how much time it would take for 100,000 items (100 times the original input). How would I solve it?

They want you to apply rule of three under ridiculous assumptions.

  If an O(n²) algorithm takes 1ms for 1000 elements, then from 1ms = c * 1000² and the ansatz Xms = c * 100000² we get that X = 10000.

In essence, they want you to assume that the running time function equals $cn^2$, in which case you could compute the constant $c$ from the given information.

The problem is that

$O(\_)$ is only an upper bound and does not tell you anything about the true behaviour of the described function,
there are unknown lower-order terms hidden in that $O(\_)$ (and also $\Theta(n^2)$, if you had that) and
asymptotics tell us nothing for any finite $n$.
They also ignore that the algorithms take different amounts of time for different inputs of the same size and
that "time" is a famously fickly cost measure as it depends a lot on effects like caching and process scheduling.

Therefore, the problem is senseless.


Finding squares touching points I am looking for an algorithm to solve the following problem:

INPUT: a set of $n$ points in the plane, $(x_1,y_1),...,(x_n,y_n)$.

OUTPUT: a set of $n-1$ axis-parallel interior-disjoint squares, such that the boundary of each square contains at least two points. (*)

Here is an example of input (left) and possible output (right) for $n=4$:

Efficiency is not a concern right now - the time complexity may be exponential in $n$ (since I will usually use this algorithm with small $n$'s).

My first thought was along the following lines:

For every pair of points, find a square that touches these two points.
In the resulting set of $n(n-1)/2$ squares, find a subset with $n-1$ squares that are interior-disjoint, or report that such a set does not exist.

The problem is that, for every two points, there may be infinitely many squares that touch them. For example, the points $(0,0)$ and $(10,7)$ are touched by any square with a side-length of 10 and lower-left corner in $0 \times [-3,0]$.

How would you approach this problem?

(*) NOTE: I don't know whether such a set of $n-1$ squares always exists. I want to play with points in order to gain some intuition about this question and maybe find a counter-example.

For a given pair of points, suppose you know which sides of the square they touch, and they are not touching the same side (of course, there are only 12 possibilities for this); fix this information about what side each is on.  For example, with your example of points at $(0,0)$ and $(10,7)$, say that we've decided that $(0,0)$ will be on the left (west) side of the square and $(10,7)$ will be on the right (east) side of the square.

It is true that there there can be infinitely many possible squares that touch those points at the given sides, as you explain in the question.  However, you can always reduce this to looking at finitely many possibilities.  In particular, I think it suffices to consider at most $2n$ candidate squares, out of this infinite set: the $n$ candidates whose bottom (south) side is at $y$-value $y_1$, $y_2$, ..., or $y_n$, and the $n$ candidates whose top (north) side is at $y$-value $y_1$, $y_2$, ..., or $y_n$.  In other words, you can consider only cases where the lower-left corner is at one of the points

$$\{(0,y_i) : i \in \{1,\dots,n\} \wedge -3 \le y \le 0\} \cup \{(0,y_i-10) : i \in \{1,\dots,n\} \wedge -3 \le y \le 0\}.$$

Of course, any square that contains some other point in its interior can be immediately ruled out.

(I don't have a proof of this statement; this is just what my intuition suggests.)

I'm not quite sure what to do if both points are on the same side (e.g., they have the same $x$-value or the same $y$-value).  Perhaps we can use a similar argument to argue that there are at most $(2n)^2$ candidate squares that must be considered, but I'm not sure.

This immediately suggests an exponential-time algorithm.  At each step, you non-deterministically select a pair of points that aren't already covered by the existing set of rectangles.  Now you're going to enumerate all candidate squares that touch those two points and non-deterministically select one such square.  To help with this, enumerate all 12 or 16 possibilities for which side of the square each point is on, and non-deterministically select one.  Next consider the $\le 2n$ candidates suggested by these possibilities, and non-deterministically select one.  This gives you a square; add it to your collection, and go on to the next step.  You can resolve the non-determinism using backtracking.  This algorithm might work well enough to experiment with many collections of points and see if you can find a counterexample for your conjecture that it is always possible to find such a set of $n-1$ squares.