texts: What is the definition of the property of Canonicity for a logic?

texts:
I'm trying to understand "A Systematic Approach to Canonicity in the Classical
Sequent Calculus" by Kaustuv Chaudhuri, Stefan Hetzl, Dale Miller. The article discusses a property called "canonicity" with respect to a logic (or perhaps just specifically for sequent calculus?).

As far as I can tell, they don't directly provide a definition for the property of canonicity. I have heard this property discussed in other contexts, and so I think this is a general property about logical systems, but I can't figure out what the precise definition is.

I think the following is a good alternative phrasing of my question: if I have a set of rules for a sequent calculus, how can I decide if that system has the property of canonicity? also, how can I decide if that system does not have the property?

EDIT: also, I think that there is a difference between canonicity and proof normalization. Is this true? What is the difference?


texts: I understand how neural networks that are implemented in software learn. You simply change the synaptic weights in the program. But how would you get a hardware implementation of neural networks to learn? The synaptic weights in the case of a physical system are INSIDE the machine, so how do you adjust the synapses? Do these neuromorphic systems require extra wires connected to every synapse (memristor etc.) in order to interface with traditional computers?


texts: Inorder tree tranversal on binary search tree doesn't give the elements in order?

texts:
I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree:

      20
    /
 10
    \
     26

However the inorder tree tranversal of this seems to be 10, 26, 20?! What is wrong here?


texts: What is the average size of a jump in a binary tree?

texts:
Assume that a full binary tree is layed out in memory recursively in the following way.
First the Root followed by Tree representation of left subtree followed by tree representation of right subtree.  Assume tree is complete and full.

If a search path requires to go from array location $a[i]$ to $a[k]$, then its referrred to as a jump and its of size $k-i$, since you travelled $k-i$ units of memory.

Given this arrangement of the tree, what is the expected size of a jump in this tree?


texts: Can I prove that I have x such that f(x) < c without revealing x?

texts:
I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob who has a powerful computer. Bob finds such an x, but he doesn't want to give it away before receiving payment from Alice, but at the same time Alice doesn't want to pay Bob before she is sure he has a sufficient value of x.

Is there a way for Bob to prove to Alice that he has such an x without revealing what the value of x is?

This can be done with a fully homomorphic encryption of f, right? For example Bob can demonstrate the equivalent inequality on the encrypted f and encrypted c for the encrypted x, and Alice can verify the encryption scheme on f and c, but this does not reveal x.

Is there any way that is less computationally expensive - even if for only certain types of functions f? Is there a partially homomorphic encryption scheme that will suffice? Or some other type of zero knowledge proof?


texts: The Partition Problem: Reducing to prove NP-Completeness

texts:
I am struggling with the below problem. Curious to hear any guidance.

The Partition Problem is the following:

$\textbf{Instance:}$ A multiset of numbers $S = \{a_1, a_2, \ldots , a_n \}$.

$\textbf{Question:}$ Can $S$ be partitioned into two multisets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Prove that the Partition Problem is NP-complete.

Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Is anyone able to help shed some light on this? Also, any explanation in plain English (maybe with some notation) would be greatly appreciated as I'm struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

Thank you in advance!


texts: Eliminating left recursion using a loop construct

texts:
I'm trying to merge a little bit of theory with a little bit of practice. I'm writing a parser-generator that generates a top-down parser based on a given grammar.
I'd like to handle left- and right recursion properly, so they would each yield the "left-recursive" and "right-recursive" tree respectively (I'm not sure if left- and rightmost derivative would be a correct term here, that would mean the whole tree). This is very important for PEG, where the associativity and order of operations is encoded in the tree. The problem is that top-down parsers can't deal with left-recursion directly.
I know the elimination rule for left-recursion, which is given a rule in the form
$A \rightarrow A \alpha_1 | \dots | A \alpha_n | \beta_1 | \dots | \beta_m$
We can rewrite it into right-recursion using  the following 2 rules:
$A \rightarrow \beta_1 A' | \dots | \beta_m A' \\
A' \rightarrow \alpha_1 A' | \dots | \alpha_n A' | \varepsilon$
This is fine for the "formal" part, but the grammar became right-recursive. To me this rule seems like it's just using right-recursion to essentially loop parts of the grammar.
So my idea was to introduce a looping construct that would account for folding the tree left. If I introduce a new postfix operator * that would mean repeating the construct 0 or more times, would the following also be a valid equivalent left-recursion elimination for A?
$A \rightarrow (\beta_1 | \dots | \beta_m) (\alpha_1 | \dots | \alpha_n)^*$
Note that since the repetition can occur 0 times, this should account for the "epsilon-case" too.
I have a strong suspicion that this is equivalent, as I did something very similar when manually parsing left-associative operators in math expressions. I'd like confirmation before introducing it in a general tool.


texts: How do I prove that all primitive recursive functions are computable?

texts: I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?


texts: Searching for an algorithm with $\Theta(n2^n)$ time complexity

texts:
I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity.
I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$.
My plan was to add a loop in the implementation, so that before you go into recursion, you are going
to count from 1 to $n$. My question is, whether my plan is successful or if I made any mistakes.


texts: Complexity of Subset Sum where the size of the subset is specified

texts:
I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.

Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a subset $T\subset S$ such that $|T|=k$ and the members of $T$ sum to $N$ ?

All of the formulations of subset sum that I've seen don't specify $k$ so I'm wondering if this problem can be solved in polynomial time. If $k$ is fixed for all instances, then I know that the problem is in P and solvable by brute force in $O(n^k)$ time. However, I'm allowing $k$ to vary from instance to instance.


texts: Searching a sorted array to find the $k$ closest values to a target value $T$

texts:
Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. Assume that $k$ is comparable, in magnitude, to $N$; i.e. we don't have $k \ll N$.

One can naively do this by first (binary) searching for the closest element, and then successively probing the left/right neighbors of that element to arrive at the result. This method has a time complexity of $O(\log N + k)$.

I suspect one can modify the original binary search algorithm to arrive at the result in $O(\log N + \log k)$ time. I tried searching online for such a variant of the binary search algorithm, without success. I'd appreciate any/all pointers to sources I might have missed, and also original attempts at formulating such a variant.

Note: It turns out there is an elegant binary search cousin that computes the result in $O(\log(N - k))$ time. See Ivan Smirnov's answer for a discussion.


texts: Propositional logic in an SMA* algorithm

texts:
I'm trying to implement an SMA* graph search algorithm that I found in a paper here(Rong Zhou, Eric A. Hansen: Memory-Bounded A* Graph Search. FLAIRS-02 Proceedings 203-209) and I would like to clarify my understanding of the pseudo-code found in the appendices, specifically the set builder notation used:

What I understand this to mean is:
make a set called B from all the elements of beta, given that beta and x are elements of OPEN, and only include the elements of beta where F(beta)<=F(x)

To test my understanding I have written this pseudo-code which I believe builds the necessary set.

x = {OPEN}
b = {OPEN}

B = {}

for i = 0; i<sizeof(b); i++
  for j = 0; j<sizeof(x); j++
    if F(b[i]) <= F(x[j])
      B.append(b[i])

My question is:

Do my plain English sentence and pseudo-code demonstrate that I have interpreted the set builder notation correctly?


texts: If a decision problem is in $P$, must finding the solution be possible in polynomial-time?

texts:
Function Problem that finds the solution

Given integer for $N$.
Find $2$ integers distinct from $N$. (But, less than $N$)
That have a product equal to $N$.

This means we must exclude integers $1$ and $N$.

An algorithm that is pseudo-polynomial

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)

for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:
  OUTPUT YES

Question

Since the decision problem is in $P$ must finding a solution also be solvable in polynomial-time?


texts: DISTINCT 3-PARTITION with all integers between $B/4$ and $B/2$

texts:
In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and $B/2$. This problem is strongly NP-hard.

The special case DISTINCT 3-PARTITION when all the integers are distinct has been studied here (at the end of the paper). The problem is also NP-hard in the strong sense. But in the definition of the instance, the authors do not include the condition that all the integers must strictly be between $B/4$ and $B/2$.

Is it clear that even with this condition DISTINCT 3-PARTITION is still strongly NP-hard?
Thank you!


texts:
I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n
}{d}$, where $k$ is the number of buckets. Then, I use SHA hash function, $H$, to find the index a bucket in the hash-table and insert the values into the bucket:

$HT [H(v) \bmod k]=v_i$

The problem is that the indices do not look uniformly at random, for instance 3 different values may map into a cell whereas an index may not appear at all. And this can lead overflow.

Notice that I need a deterministic way as two different parties encode their values using hash table. Therefore, if the parties use the identical parameters for hash table, the same values should be in the same bucket (of different hash tables). Obviously different party may have different set values.

Question: What is the best way of preventing overflow in the above scenario?


texts: Wagner Fischer Algorithm and the Empty String

texts:
In the Wagner Fischer algorithm to calculate the Levenshtein distance for two input strings, the first step is to compare each input string with the empty string for each input. Why is this step necessary? Is the purpose simply to keep the algorithm consistent when checking the strings for matches and mismatches to determine the distance between two prefixes?

Thanks!


texts: What is the time complexity in big-O notation of Algorithm X?

texts:
Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)

I do not understand how such algorithm could do that. What is the time complexity of this algorithm in terms of big-O notation?

Here is the algorithm from Wikipedia.

  If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
  Otherwise choose a column $c$ (deterministically).
  Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
  Include row $r$ in the partial solution.
  For each column $j$ such that $A_{r,j} = 1$,

  for each row $i$ such that $A_{i,j} = 1$,

  delete row $i$ from matrix $A$.

  delete column $j$ from matrix $A$.

  Repeat this algorithm recursively on the reduced matrix A.

Step 3 of the algorithm is done nondeterministically. What does this mean? (I think this is the point why I cannot find the big-O complexity of the algorithm.)

An implementation of Algorithm X in python can be found in Algorithm X in 30 lines! where I cannot find the nondeterministic choice of step 3.


texts: What exactly can finite-state machines not do?

texts: I know finite-state machines can be used to solve yes/no kind of problems, such as finding whether a word is in language or not. Can somebody tell me exactly what FSM cannot do and why?


texts:
Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way to delete A[index] and update the values accordingly in F[] would be to perform update(index, -A[index]), then set A[index]=0. However, I could imagine that after a few deletes, the tree would be quite inefficient with all the 0s floating around.

We could compress the tree at each deletion by shifting the values down in A[] after A[index]=0 and rebuilding F[index:n] by referencing A. However, this solution is worst case O(nlogn) time, and I feel like if there was a way to rebuild F[index:n] using values in F[], this could be much more efficient. Unfortunately, the literature online seems a bit sparse on the deletion front. Any ideas?


texts:
L={ | M is a DFA, |w| is even for all w in L(M)}

Meaning we are looking for a Turing Machine or any algorithm that receives a description of a DFA and decides if all the words this DFA accepts are even in there length(length of 0, 2, 4, 6 ..). DFA stands for Deterministic Finite Automata. My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.For example 0011 has even length, 0 takes you to state2 0 state3 1 state4 1 state5. because when you start you are already at state 1(Qstart).

My question: is my solution solid, is it right? Does it run in Polynomial time?
I think running time is: o(n^2)


texts: "Smallest set" term in the trees set definition

texts:
I often meet such kind of the definition of the set of trees, as:

The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a\in\Sigma$ and $w\in T^*$, $a(w)$ is in $T$. (http://dl.acm.org/citation.cfm?id=2101368)

One question that I can not generally understand is: how does this definition prevent from the string, say "$a)($", appear in the set $T$?

Would somebody be so kind explain me this point?

And please, if you are going to downvote this question, be so kind explain why are you doing that.


texts: Nisan-Wigderson generator and $\mathbf P=\mathbf{BPP}$

texts:
In this set of notes it is claimed that:

If there exists a polynomial-time pseudorandom generator $G:\{0,1\}^{O(\log n)}\to\{0,1\}^{O(n)}$ that $1/10$-fools all $n^2$-size circuits, then $\mathbf P=\mathbf{BPP}$.

The proof of this is as follows: If a language $L$ is in $\mathbf{BPP}$, then there is a polynomial-time algorithm $A$ such that
$$
x\in L\implies \Pr(A(x,y)=1)>\frac23;\\
x\not\in L\implies \Pr(A(x,y)=1)<\frac13,
$$
where the probabilities extend over random strings $y$ of length polynomial in the length of $x$.
Then consider the following deterministic algorithm $B$ that:

Enumerate over all seeds $z\in\{0,1\}^{O(\log n)}$.
For each $z$, call $A(x,G(z))$.
Return $1$ if strictly more than half of the calls return $1$, otherwise return $0$.

It is clear that $B$ is deterministic and polynomial-time. However I'm somewhat confused on the rigor of this proof. The proof is predicated on the idea that since $G$ is a pseudorandom generator, $A$ is unable to distinguish between the output of $G$ and the uniform distribution, hence for an input $x\in L$ we would have $\Pr_{z\sim\{0,1\}^{\log n}}(A(x,G(z))=1)>2/3-1/10>1/2$.
But by assumption $G$ is only able to fool circuits of size $n^2$. What if $L$ is not recognizable by circuits of size $n^2$ (or, if $A$ cannot be represented by circuits of size $n^2$)?


texts: Help with understanding why we need an expectation in the loss

texts:
I am reading the paper SV2P - Stochastic Varaiational Video Prediction (https://arxiv.org/abs/1710.11252). In it the authors use the loss shown in the image:

Why do we need expectation in the reconstruction loss?
I think that the loss is similar to the one used in the VAE paper.


texts: Why isn't this undecidable problem in NP?

texts:
Clearly there aren't any undecidable problems in NP.  However, according to Wikipedia:

  NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that are] verifiable in polynomial time by a deterministic Turing machine.

  [...]

  A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Now consider the following problem:

  Given a Diophantine equation, does it have any integer solutions?

Given a solution, it's easy to verify in polynomial time that it really is a solution:  just plug the numbers into the equation.  Thus, the problem is in NP.  However, solving this problem is famously known to be undecidable!

(Similarly, it seems the halting problem should be in NP, since the "yes"-solution of "this program halts at the N-th step" can be verified in N steps.)

Obviously there's something wrong with my understanding, but what is it?


texts: Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?

texts:
The following process seems to be a recurring one:

Initial design. Commercial organisations invent and implement a design that seems at the time to work.
Problem discovered, new design suggested. Due to new developments, or just because the designers missed something, a problem with the design is discovered. Academics find a solution to the problem, and a new design is proposed.
Old, sub-optimal design persists due to existing production. However, the original sub-optimal design is maintained, because a large amount of devices with the old design are already deployed, and for various reasons (network effects, the need for compatibility between devices, etc), this means producers don't want to switch. Or alternatively, new production switches, but we still have to deal with the old design because of the large already produced devices.

I am looking for historical examples of such a process in the context of the IT security of CPU/instruction-set-architecture:

What designs of instruction sets/CPU's are we stuck with that are bad from a security perspective, but that are maintained because the cost of switching is high? (I can imagine that this is also intertwined with OS design and internet protocols).


texts: Meaning of the univalence axiom on plain data types

texts:
I'm trying to wrap my head around HoTT and can't figure out the intuitive meaning and validity of the univalence axiom.  IIUC this axiom says:

UA: ∀ A,B:Type . (A = B) ≃ (A ≃ B)

where X ≃ Y is a shorthand for (X → Y) ∧ (Y → X).

When I take A and B to be propositions, this makes a lot of sense: it basically gives my that two equivalent propositions can be considered as equal, and given some form of proof irrelevance it makes perfect sense.

But how can it make sense when A and B are, say nat and bool, for example?  I can trivially define a function of type nat → bool as well as a function of type bool → nat, yet it doesn't make sense to me to state that nat = bool.  So is there some detail of the definition of UA that prevents its use on things like nat/bool, or does it really also apply in this case, in which case does it mean that the usual understanding of the refl elimination needs to be refined so it's not just a sort of type-cast any more but has potentially non-trivial computational content?


texts:
Given:

graph with colored edges;
list of $\alpha$ colors;
list of $\epsilon$ colors;
clique size $k$.

Problem:

Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?
Isn't there an edge of some of $\epsilon$ color that is not contained in clique of size $k$?

Example:

Given some graph that has blue, red, green and magenta edges.

$\alpha$ colors: red, blue.

$\epsilon$ colors: green, magenta.

Answer is yes if both conditions are satisfied:

All red and blue edges are contained in cliques of size $k$ (or larger, of course).
There exists at least one green and at least one magenta edges that are contained in some cliques of size $k$.

Here are 2 special cases, for both $n = 10, k = 4, \alpha$: red and blue, $\epsilon$ - green and magenta. The only difference is color of edge BE.

1st graph satisfies the conditions: all red and blue edges are contained in 4-vertex cliques ABIH, FGIJ, CDEF as well as they contain at least one green and at least one magenta edge.

2nd graph doesn't satisfy the conditions because blue edge BE is not a member of 4-vertex clique.

I think this problem is PSPACE-complete but I'm not sure about reduction from TQBF to this. If such reduction is possible, it is not similar to known SAT to max-clique reduction.


texts: Difference between present - absent bit and valid - invalid bit in a page table?

texts:
while reading I found this:

  Present/Absent bit – Present or absent bit says whether a particular page you are looking for is present or absent. In case if it is not present, that is called Page Fault. It is set to 0 if the corresponding page is not in memory.

and

  Valid and Invalid bit are present in the page table of concern process and it indicate whether address generated by cpu is valid or invalid and tells whether the address generated belongs to process address space or not.

Also since the page table contains only the page entries for a process so how come V/I bit present in page table tell that the generated address is not valid for the addresses not present in process.

I am a beginner, so please help me build my concepts.


texts: Performance impact due to time required for shuffling in Quicksort

texts:
As a programmer with non CS background, I am learning algorithms.

When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the time/space needed for shuffling. I do understand that shuffling is important to have the $O(n\log n)$ performance, but shuffling itself would have a complexity of $O(n)$. Why does this become irrelevant in the total performance?


texts: NP-complete problem whose corresponding optimization problem is not NP-hard

texts:
For this question I will refer to$\ NP-hard$ problems as those that are at least as hard as$ \ NP-complete$ problems. That is, a problem$ \ H$ is$\ NP-hard$ if there is an$ \ NP-complete$ problem$\ G$, such that$\ G$ is reducible to$\ H$ in polynomial time.$\ NP-hard$ problems are not restricted to decision problems and are not necessarily in$\ NP$.

Considering the above, is there any optimization problem$\ L$  such that$ \ L \notin NP-hard $ and whose corresponding decision problem is$ \ NP-complete$?

For example, consider the case for the travelling salesman problem. (TSP)

  Optimization problem: Given a list of cities and the distances between each pair, what is the shortest path that visits each city and returns to the original city?

  Decision problem: Given a list of cities, the distances between each pair and a length$ \ L$, does there exist a path that visits each city and returns to the original city of length at most$\ L$.

It is well known that the decision problem of TSP is$ \ NP-complete$ and its corresponding optimization problem is$\ NP-hard$.

To sum up, what is an example of a$\ NP-complete$ problem whose corresponding optimization problem lies outside the class$\ NP-hard$? Perhaps, it is$\ EXPTIME$.


texts: Complexity bounds for Turing equivalence

texts: I am looking for bounds - both lower and upper - on the time and spacial complexity of simulating Turing-complete systems with each other. (I am aware that both time and space are ill-defined with many systems. However, I do not know of a better way of describing them.)


texts: Algorithm for segmenting input query into query/join tree

texts:
Wondering what algorithms look like for implementing a complex JOIN query handler. Taking a look at this paper Building Query Compilers they talk about Query Graphs and Join Trees and Cost Functions for determining how well join trees are when the engine figures out how to organize the steps in the query.

What I'm particularly looking for is the part of how they segment the input query into the query/join tree. Specifically, this relates to scheduling and queries. I understand how the cost functions work. I just don't understand how you take a relational algebra query tree and break them apart into distinct chunks of operations sequenced together. They usually just say "we have a query x and here is the corresponding tree":

without a description of how the tree was obtained.

I'm confused as to why they would break apart conditional statements, and how they know where to break them apart, and how to order them (when do heuristics apply, etc.)

What follows is a brief overview of the algorithm, showing where I am confused.

Given a query tree as input, we first convert it to CNF. Then we construct a query graph, which is a graph over the WHERE + FROM portions of the query. This graph is only used for determining if the query is correct or not in some cases. Otherwise we can skip the query graph. Then we construct the JOIN tree by x... This is what I'm wondering. In the following algorithm it would be the last part.

\begin{align}
& \texttt{Input}\ Q: \texttt{QueryTree} \\
& \texttt{Output}\ Q''': \texttt{JoinTree} \\
&   \texttt{Begin} \\
  &   X : Q \rightarrow Q'\ //\ convert\ to\ CNF \\
  &   G : Q' \rightarrow Q''\ //\ convert\ to\ query\ graph \\
  &   Validate\ Q'' \\
  &   J : Q'' \rightarrow Q'''\ //\ convert\ to\ join\ tree (confused here) \\
  &   Return\ Q''' \\
&   \texttt{End}
\end{align}

The question is, how a database query engine goes through and figures out the order of operations.


texts:
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

I saw this Gurobi post that uses Integer Linear Programming to solve the traveling salesman problem.

I compared its runtime with a Backtracking algorithm written in python, and the Integer Linear Program seems to be faster?

Is the Integer Linear Program faster because Gurobi is implemented in C++ or is it faster because it uses heuristics, pruning and other optimizations to improve its runtime?


texts: BPP search: what does boosting correctness entail?

texts:
It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how it works?

With BPP search, I mean a problem that can have false positive-negative, correct solution, and no-solution. Here's a definition:

A probabilistic polynomial-time algorithm $A$ solves the search problem of the relation $R$ if

for every $x ∈ S$, $Pr[A(x) ∈ R(x)] > 1 - μ(|x|)$
for every $x ∉ SR$, $Pr[A(x) = \text{no-solution}] > 1 - μ(|x|)$

were $R(x)$ is the set of solution for the problem and $μ(|x|)$ is a negligible function (it is rare that it fails).

So now I would like to increase my probability of getting a good answer, how can I do it?

~ ".. boosting for correctness.." : a way to increase the probability of the algorithm (generally by multile runs of the probabilistic algorithm), i.e., when the problem have a solution then the algorithm likely return a valid one.


texts: Set data structure for data too large to fit into memory

texts:
I'm trying to solve the following exercise:

  Given N data items and memory that can hold M/B blocks of size B.
  Describe a data structure that needs at most N/B blocks of external memory and allows us to answer questions of the form "$s \in S$?" using $\log_BN$ I/O operations.

We may assume a static set, i.e. we do not care for efficient insertion or deletion of elements to or from the set and do not care for efficient creation of the data structure. Furthermore, M and B are known.

If the data is ordered, I could sort the data using e.g. MergeSort for external memory, then partition the sorted data into N/B sections and create a B-tree, where each node consists of a block of memory with elements containing a value of the set and an external memory location pointing to the block which contains all elements larger or equal to the value and smaller than the value of the next element in the parent block. In that case we would need $N/B$ external memory locations to store the block and $\log_B N$ I/O operations to search for a value.

My question is about how one would handle non-ordered data? I don't see how one could encode the data as a numeric value and then use the B-tree construction.


texts: Negation of the semantics of the Until operator in LTL

texts:
I have been looking at the Until operator and the release operator and when introduced to the release operator it was suggested that it is equivalent to:

$\phi R \psi \equiv \neg(\neg\phi U \neg \psi)$

But when trying to get from the semantic definition of the Until operator to the semantic definition of the Release operator by negation I get stuck part way. Specifically, I get stuck trying to negate a $\forall j < i$ expression as I will show below.

So the semantic definition of Until:

$\pi \models \phi U \psi \iff \exists i \geq0, \pi[i] \models \psi \land \forall j\leq i-1, \pi[j]\models \phi$

Putting the negations in:

$\pi \models \neg(\neg\phi U \neg\psi) \iff \neg(\exists i \geq0, \pi[i] \models \neg\psi \land \forall j< i, \pi[j]\models \neg\phi)$

$\iff \forall i \geq 0, \neg(\pi[i]\models\neg\psi)\lor \neg(\forall j < i,\pi[j]\models\neg\phi)$

$\iff \forall i \geq 0, (\pi[i]\models\psi)\lor (\exists j < i,\pi[j]\models\phi)$

In words, I am ending up with globally $\psi$ or globally there always exists some predecessor that satisfies $\phi$. Which cannot be correct as $\pi[j]$ is not defined when $i=0$.

The semantic definition for the release operator that I was aiming for is:

$\pi \models \phi R\psi \iff (\exists i\geq 0, \pi[i]\models\phi \land \forall j\leq i, \pi[j]\models\psi)\lor (\forall k \geq 0, \pi[k] \models \psi)$

So I have part of the expression correct ($\forall k \geq 0, \pi[k] \models \psi \equiv \forall i \geq 0, (\pi[i]\models\psi)$), but I am really stumped about how to get the second part or where I went wrong.

Any help enlightening me is greatly appreciated!

Thanks!


texts:
Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost.
The image bellow is an example of a possible solution for that map, then the output of the algorithm should be two trees with the edges of those trees.

If there is only one factory a possible solution would be using Kruskal's algorithm to find the MST with this factory as source.

¿Is there any algorithm to do so? ¿How would a modification of Kruskal's work?

[EDIT]
I need to find the minimum cost tree from factories to shops but given that there is more than one factory may have unconnected trees as optimal solution.

[EDIT 2]
If an edge is used twice that cost counts only once.


texts: Efficiently generating a uniformly random list of unique integers in a range

texts:
The problem:

To generate a list of size $n$,
Containing unique integers,
Sampled uniformly in the range $\left[0,m\right)$,
In $O(n)$ time, except that:

Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.

Apologies if this is a duplicate, if you find one, feel free to point it out.

EDIT: to clarify, the question implies that we are concerned the complixity in terms of bit-operations. (See logarithmic cost model).


texts: Why isn't a valid bit used for associative cache in processors

texts:
Direct map cache uses a valid bit to effectively know if any data is present to a specific cache-slot (aka line/index). If this is the only use of this bit, then I believe, once a line has v-bit set, it won't be unset until power off.

In addition, I wonder why similar optimization has not been done for associative (full or k-way) cache. Only reason I could imagine is that since for every read/write, a cache-slot will be filled, the cache will be filled pretty soon; and the probability of a slot being empty is zero in no time.

Any feedback will be much appreciated.


texts: Why are decision problems easier than the equivallent optimization problems?

texts:
Suppose that we have an optimization problem defined as follows:

$OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$

and the equivallent decision problem

$L_{OPT}$ = Given an input string defining $F$ and $f$ and a target value $u\in Q$, decide if there is a solution $x \in F$ so that $f(x) \geq u$

Assuming that an efficient solution here is defined as an algorithm that runs in polynomial time in the length of the input, then if we have an efficient solution for $OPT$ it is trivial to see that we can get an efficient solution for $L_{OPT}$. However, my teacher said that we could have that $L_{OPT}$ has an efficient solution without $OPT$ having an efficient solution.

How is the latter possible? If we can efficiently solve $L_{OPT}$, wouldn't we be able to run a binary search algorithm to find the solution for $OPT$?


texts: Hardware Transactional Memory Operations in a Hyperthreaded Core

texts:
If I had a single core with other cores that have access to a BUS the problem of transactional memory makes sense with the setting of the T bit and letting cores be able to see the caches of the other cores so they know if they're working on shared memory and they can therefore resolve the conflict.

The problem I'm having is understanding how this works in a hyperthreaded core. Does the core share the cache and split it into two? Does the cache line have 2 T bits instead of 1 to differentiate which "Core" is using which resource in the cache?

I have these guesses but can't find any definitive answers anywhere.


texts: What is the definition of Computer Science, and what is the Science within Computer Science?

texts:
I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to pursue.

Having said that, there seems to be a variety of definitions about what Computer Science really is in respects to academia, the private-sector, and the actual "Science" in "Computer Science" I would love to have answers(Or shared pondering) as to the breadth of things an education in Computer Science can be applied to, and ultimately the variety of paths those within Computer Science have pursued.


texts: Hamiltonian path and minimum spanning tree

texts:
Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to find the Minimum spanning tree

but

in declarative language(specially prolog, we can apply same algorithm but those are limited) , If i want to find a minimum spanning tree on the same graph, If i collect all possible hamiltonian paths using findall/3 predicate then chose the one with smallest accumulated cost, is it then also a minimum-spanning-tree?

More specifically , Can we transform the problem of finding minimum spanning tree to the hamiltonian path finding problem but not in other direction?  Because normal algorithms return one specific minimum spanning tree of a graph but i am more interest in finding more than one minimum spanning trees.


texts: What is the origin of using Q to denote a set of states in an automaton?

texts:
When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc.

Is there a particular reason why the letter $Q$ was chosen? As in, is $Q$ the first letter of a word historically related to automata? Or was it chosen totally arbitrarily?


texts: What is the definition of a $\Pi_1$-sentence?

texts:
What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence?
I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall n_2\dots\forall n_k \psi$ where $\psi$ is a formula in the language of Peano arithmetic with only bounded quantifiers. And for the analytical hierarchy, a $\Pi_1^1$-sentence  is a sentence of the form $\forall X_1\forall X_2\dots\forall X_k \psi$ where $\psi$ is a formula in the language of second-order arithmetic with no set quantifiers.

I found the following definition for this notation in section "5 Proving Independence" of an article on the possibility of undecidability:

  Let’s define a $\Pi_1$-sentence to be any sentence of the form, “For all $x$, $P (x)$,” where $P$ is function that can be proven to be recursive in Peano Arithmetic, PA.

People talking about $\Pi_1$- and $\Pi_2$-sentences sometimes refer to Shoenfield's absoluteness theorem, which seems to talk about $\Pi^1_2$-sentences, i.e. refers to the analytical hierarchy. Can I deduce from this that people talking about $\Pi_1$-sentences use $\Pi_1$ as a shorthand for $\Pi^1_1$ (because $x^1=x$...)? But the quoted definition looks much more like the condition from the arithmetical hierarchy to me, even so I'm not sure whether it is really equivalent to it.


texts:
We have an array of $N$ positive elements. We can perform $M$ operations on this array. In each operation we have to select a subarray(contiguous) of length $W$ and increase each element by 1. Each element of the array can be increased at most $K$ times.
We have to perform these operations such that the minimum element in the array is maximized. In other words, after these operations minimum element in the array should be as large as possible.

$1 \leq N, \ W \leq 10^5$

$1 \leq M, \ K \leq 10^5$

Time limit: 1 sec

I can think of an $O(N^2)$ solution but it is exceeding time limit. Can somebody provide an $O(NlogN)$ or better solution for this?

P.S.- This is an interview question


texts: Linear Temporal Logic (LTL) Syntax Infinitely Often

texts:
I'm a little confused about some LTL syntax.

When the Global and Future operator (GFx) or []<>x is used, what does it mean. In the lecture slides it is given as infinitely often. But I don't understand it.

When used as FGx or <>[]x, I understand it as eventually in the future something will be true forever. E.g. eventually x will become 3 (x = 3) and x will stay as 3 forever.

Can someone explain what GFx means?


texts: How to prove an polynomial run time is faster than exponential using definition of big O

texts:
This is for homework so feel free to not give me an answer but steer me in the right direction.

The problem states:

  Prove that $n^{1000000} = O(1.000001^n)$ using the formal definition of Big-O.

The definition of Big-O is:

$\hspace{2cm}T(n)=O(f(n)):\,\exists\;c\gt0\;$ and $\;n_0\ge0,\;$ such that $\;T(n)\le c\cdot f(n)$

Now, I know that there is also the definition that

$\hspace{4cm}$For every $\;r\gt0\;$ and $\;d\gt0,\; n^d = O(r^n)$

But how exactly am I supposed to prove this without using induction or a limit equation? Any guidance on where to start?

This is what I have so far:

$\hspace{7.6cm}\frac{T(n)}{f(n)}\le c$

$\hspace{6.8cm}\frac{n^{1000000}}{1.000001^n}\le c$

$\hspace{6cm}\frac{1.000001^{1000000n}}{1.000001^n}\gt\frac{n^{1000000}}{1.000001^n}$

EDIT: I continued simplifying.

$\hspace{5.4cm}1.000001^{999999n}\gt\frac{n^{1000000}}{1.000001^n}$

Do I stop here?

$\hspace{5.3cm}1.000001^{1000000n}\gt n^{1000000}$

$\hspace{3.4cm}1000000n\cdot log(1.000001)\gt 1000000\cdot log(n)$

$\hspace{5.8cm}log(1.000001)\gt \frac{1}{n}\cdot log(n)$

$\hspace{6.8cm}1.000001\gt n^{1/n}$

What would the above even tell me?


texts: Does there exist a Reed-Solomon-like code over decimal symbols?

texts:
A Reed-Solomon error-correcting code consisting of N symbols is guaranteed to detect up to N single-symbol replacements in an arbitrarily long input plus the ECC itself, and is also guaranteed to correct up to floor(N/2) single-symbol replacements in the same.

I can't claim to understand the math behind Reed-Solomon ECC, but I notice that all the implementations I could find operate on symbols in base 16, 64 or 256. This seems to suggest that 1024 etc. are also bases in which this scheme can operate with the right polynomial.

Is it possible to have an ECC scheme with exactly the above properties that operates on decimal symbols? Can Reed-Solomon be trivially adapted for this purpose?

(this question is prompted by my answer to a puzzling.SE question)


texts: Shortest decimal expansion within binary interval

texts:
Consider an interval $[x-2^n,x+2^n]$ defined by a binary float $x$ and a power of two $2^n$ typically much smaller than $x$. I would like to know whether an efficient algorithm exists to determine the shortest decimal expansion within the interval. What is the basic idea of such an algorithm? Perhaps such an algorithm has already been published?

In my own search, I have come across the work of Steele & White “How to print floating-point numbers accurately”, but it is not clear to me whether it applies in the sense that their results can be adapted to this particular case.


texts:
Below is my solution. Is this sufficient enough to prove?

$$|x^3+5x| \le |x^3+5x^3|$$

$$x^3 + 5^x \le 6x^3, x > 1, C=6$$

Let's take $x = 2$.

$$f(x) = (2)^3 + 5(2) = 18$$

$$g(x) = 6\cdot 8 = 48$$

For when $x > 1 |f(x)| \le C|g(x)|$ is false hence proving $x^3 + 5x$ is not $O(x^2)$.


texts: What does "number of gates" mean in circuit complexity?

texts: By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.


texts: What do the symbols M and N mean in this definition of lambda terms?

texts:
I am learning lambda calculus from the book https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and do not understand the meaning of the following symbols.

The definition of the lambda terms is:

Lambda terms: $\mathit{M,N} ::= x | (M N) | (λx.M) $

The question is, what do $\mathit{M}$ and $\mathit{N}$ mean?


texts: Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $

texts:
How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}.

My try:
Construct a Turing machine $N$ using a Turing Machine $U$ that decides universal language as subroutine to decide $L_c$.
$N$, on any input $  <\langle M_1 \rangle, \langle M_2 \rangle >$:
$1.$ Construct a program that generates word $w \in \sum^\ast$ in canonical order.
$2.$ Run $U$ on $\langle M_1, w\rangle $ and $\langle M_2, w\rangle $.
$3.$ If $U$ accepts both, accept.
$4.$ If not, back to $1$.

It seems does not work. Because if $L(M_1)\cap L(M_2)= \emptyset$, $N$ will loop forever(it just can't find such $w$).


texts: What is the name of the following linear solver

texts:
I am trying to understand Jos Stam's method for simulating stable fluids.
Here on page 21 he explain that he want to solve the following linear system:
Y[i,j] = (1+4a)*X[i,j] - a*X[i+1,j] - a*X[i-1,j] - a*X[i,j+1] - a*X[i,j+1]

He also discusses some possible linear solvers to use in this case (trying to take advantage that of the fact that "A" matrix is sparse).
I looked at his code and see this implementation (rewrote as pseudo code for clarity):
for ( k=0 ; k<20 ; k++ ) {
    FOR_EACH_CELL
        X[i,j] = (Y[i,j] + a*(X[i-1,j] + X[i+1,j] + X[i,j-1] + X[i,j+1]))/(1+4a);
    END_FOR
    set_bounds(X);
}

I have difficulty understanding this piece of code. How using the X values which are partially calculated and partially not is beneficial.
If I knew the name of the linear solver algorithm used here I could look it up and and get more information.


texts: Why is tabulated hashing 3-wise independent but not 4-wise independent?

texts:
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $w$-bit strings (or $2w$-bit strings broken in half), and hash values are
$l$-bit strings.
Let $A[0 \cdots 2^w-1]$ and $B[0 \cdots 2^w-1]$ be arrays of $l$-bit strings. $A$ and $B$ can be though of as $2^w \times l$ dimensional array of bits.
Define the hash function $h_{A, B} : \mathcal{U} \to [m]$ by setting $h_{A, B}(x, y) = A[x] \oplus B[y]$, where $\oplus$ denotes bit-wise exclusive-or.
Let $\mathcal{H}'$ denote the set of all possible functions $h_{A, B}$.
Can someone explain  why is  $\mathcal{H}'$ 3-wise independent and not 4-wise independent?


texts: How is the literal meaning of "rendezvous" related to its usage in distributed computing?

texts:
I am trying to figure out the difference between RPC and Rendezvous.  Is it correct that they differ only on their implementation on server side: RPC will involve creating a new process/thread to handle a request, and Rendezvous will pick an existing process/thread to handle a request?

The word "rendezvous" simply means a bunch of people meeting together. How is it related to its usage in computing?

Thanks.


texts:
What is the purpose of point clouds in machine learning?

Consider the following suggestion:
Say I have a table (per year) of records (such as days) each of which is made of n real numbers such as temperatures per hour). Can I use the table as a data point to do classification of the year as hot/cold or something like that?

Any real-world examples of point cloud data?


texts: Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?

texts:
When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a  reduction that fulfills the following property:
If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is also $\Sigma_i^P$ or $\Pi_i^P$.

I can see how Karp-reductions fulfill this requirement for the complexity class $P$. How could one proof that Karp-reduction fulfill this requirement for all other complexity classes in the polynomial hierachy?


texts: Optimal algorithm for finding all ngrams from a pre-defined set in a text

texts:
I'm thinking about the optimal algorithm for the following problem:

Input data:

a text, say it's an article about 5-50 pages.
a set of ngrams (ngram strings, n>2), of arbitrary length, could be more than 20k n-grams.

The algorithm should output the following:

a dictionary of all ngrams that were found in the text with the corresponding quantities, it should also take into account that ngrams could partially intersect or consist of each other (like 'probability density', 'probability density function', 'probability density distribution')

So the question is what would be the most time-efficient algorithm to compute this?

Both all words in a text and all words in ngrams are reduced to the canonical forms.


texts:
I want to prove that $ L = {a^n b^m c^{ \lfloor \frac{n}{m} \rfloor } }  $

isn't context free language, so I choose N - constant from lemma

so the word is
$ w = a^N b^N c $  and $ w = uvxyz $

1 case

v and y contains only a
$ v,y \in a^{*} $

and $ w_2 = a^{N+B} b^{N} c $ where $ B > 0 $
is it correct to say that it doesn't belong to language, because $ N + B \neq N $ ?

edit

or second version

$ v,y \in a^{*} $
so $w_0 = uv^0xy^0z = uxz $ and $ w_0 = a^{N-B}b^Nc $ which doesn't belong to language because $  \lfloor \frac{N-B}{N} \rfloor = 0 \neq 1 $

and what with case where $ v \in a^+ $ and $ y \in b^+ $


texts: Minimum give away on performance based queue?

texts:
I'm trying to solve algorithm problem, so far no luck

Lets imagine A is an employer and there are N employee currently on line (queuing) for receiving their paycheck of the month, and each of the employee are given the same base salary, $1000 each, but their bonuses are based on their performance and where they are right now on queue line. As employer, A want to minimize the bonus for whole employees, so the company can save money.

So if the input is an array of employee and their performance metric, where index 0 is first on queue, and so on.

The employer want to see the output that indicate on how much each employee will receive as bonuses, and the bonuses are calculated with following rules:

Bonuses given are the minimum possible payout to employee, with the restrictions below.
An employee can receive no bonuses at all, i.e: USD0
Bonuses are in the multiple of USD100, i.e: USD0, USD100, USD200, USD300, so on
Between any two employee that are next to each other in queue line the bonus must reflect their performance, i.e: the higher of the two s receive higher bonus, and vice versa.
Two employee that are next to each other in queue line can have same bonuses/not receiving bonuses if they have the same performance metric.

So, for example, if the input is [9,7,1,2,1,1,7,4,6,1,7,8,6,2,2,1,1] and the value of employee performance metric was restricted to >=1 and <=10.

We could expect the output be like [200,100,0,100,0,0,100,0,100,0,100,300,200,100,100,0,0]

Here other input and output example:

    input = [9,8,7,6,5,4,3,2,1,7,8,9,1,1,1]
    output = [800,700,600,500,400,300,200,100,0,100,200,300,0,0,0]

    input = [3,5,4,7,8,6,4,4,5,7,7,6,2,2,2,3,4]
    output = [0,100,0,300,200,100,0,0,100,200,200,100,0,0,0,100,200]

Thanks.


texts: What information and usefulness does knowing the consensus number of a shared object give me?


texts:
I am a domain scientist and I study biophysical systems. When I asked a colleague in CS for suggestions about how to design a multi-scale simulator, he mentioned the term "compact model".

Now, I can't find a very good definition of this term. I can find the book "Compact Modeling" edited by Gildenblat but this is a collection of domain specific applications, similar to what I found on google scholar.

I haven't found a first-principles treatment of what a compact model is or the advantages of using one. It would be great to know where I could find this topic in a textbook or annual reviews type paper.

Q: What is a compact model, and when is it useful?


texts: Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

texts: I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this notation can be reversed? that is, can I write this down like $A\ge_p B$ And still have a meaning? I searched a lot but this notation always been like the former and I got confused.


texts: How to prove that for a decidable problem the problem and the compliment of the problem are semi-decidable?

texts: Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable?


texts:
This is a general question and one that has bugged me for a long time.
I want to start working on an artificial universe, not something too ambitious but more of a basic concept. What I have in mind is a simulation that has a sense of time, has physics rules, some beings that interact with each other and are able to learn to some extent, in a top-down, 2D world. In addition to this, it might have a visualization of what is going on, like a game.
I didn't succeed in finding a work or guide on this topic. The questions are:
What should be the approach to building such a simulation?
Are there any resources that can help me get started?


texts: Can both $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$ happen at once?

texts:
For which case are both $f(n) \ne O(g(n))$ and $g(n) \ne O(f(n))$ true?

I have following answer to this which I could not understand:

  Sometimes true: For $f(n) = 1$ and $g(n) = |n \sin n|$ it is true, while for any $f(n) = O(g(n))$, e.g. $f(n) = g(n) = 1$, it is not true.

Please someone help in understanding:

For which case is it sometimes true? An explanation with example will be much appreciated.
What is meaning of "||" in this?


texts: Which language is accepted by this Muller Automaton?

texts:
In my opinon the Language recognised is this:

$(a + b)^* (ab)^ω$
but the solution provided is: $(a + b)^* (a + b)^ω$

Did I missunderstand the acceptance condition or is the solution wrong?

My reasoning is:
As far as I understood a Muller Automaton does accept a run if all the set of all infinitely often visited states can be found as acceptance condition.E.g. if a run visits inf. often the states p & r and finitely often q then the set { p , r } has to be one of the set's of the acceptance condition.

I think in this case, that a word has to bounce inf. often between 2 of the 3 states (but is not allowed to visit the 3rd state inf. often). That means that in the end the word has to alternate between a & b inf. often after doing finitely often whatever it want's to do
=> $(a + b)^*$ ( = "do what ever you want to do finitly often and in the end") $(ab)^ω$ (= "iterate between a and b")

The given solution differs from my solution by accepting e.g. the following word:
$aba^ω$


texts: Prove that context free languages aren't closed under DropMiddle

texts:
The question is simple:

$\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$.
Prove that CFL's aren't closed under $\operatorname{DropMiddle}$.

I should probably be looking for a counter example, but I'm coming up short. I know that the language $ww$ ($w$ is a word in some CFL) isn't a CFL, but I can't figure out if I'm on the right track at all.


texts: Does RLNC (Random Linear Network Coding) still need interaction from the other side to overcome packet loss reliably?

texts:
I'm looking into implementing RLNC as a project, and while I understand the concept of encoding the original data with random linear coefficients, resulting in a number of packets, sending those packets, and thus the client will be able to reconstruct the original data from some of the received packets, even if a few of the packets are lost, if enough encoded packets have arrived to create a solvable equation system.
However, I have not seen any mention of the fact that if there is a non zero percent of packet loss, there is a possibility that the receiver of the encoded packets will not receive enough packets to reconstruct the original data. The only solution I see to this is to implement some type of sequencing so that the receiver can verify he hasn't missed some packets that would allow him to reconstruct the original data, in other words interaction. Am I missing some part of the algorithm or not? If someone has solved this problem already, can you please show me where it has been solved so I can read about it?


texts:
There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it.

Graph $G$ is a $k$-tree if it's possible to divide all it's edges to $k$ trees ($k$ subgraphs without a loop). Given network $N$ every processor knows it's parent and it's children in every tree. Using algorithm for 3-coloring of an arbitrary tree (as describe in Vertex Coloring) show that the given graph $G$ is $3k$-colorable in the same time complexity $O(\log^*n)$.

Ideas: every vertex $v$ could belong to one or more trees among $k$ trees. For every particular tree vertex $v$ belongs to, vertex $v$ knows it's parent in this tree and it's children in this tree. Exercise asks to color a graph $G$ in $3k$ colors.   Running the mentioned algorithm for any particular tree we will get correct 3-colorable $k$ trees, each vertex will have $m$ different color labels, where $m$ is number of trees, vertex $v$ belongs to.

Now the difficult part, concatenation of all $m$ color labels in one color for vertex $v$ will result in $3^k$ different colors for graph $G$.

In general, simplification of the problem is on the picture.

Vertices $v$ and $u$ are connected by an edge (on the picture the edge belongs to the 1 tree, in principle it doesn't matter, we could draw a parallel edge that belongs to 2 tree), $v$ and $u$ belong to 1 tree and 2 tree. After running 3-colorability algorithm for every tree we will get the correct colorability, now the problem is to make color assignments to vertices $v$ and $u$ as vertices of the graph $G$ based on the color assignment of these vertices for 1 tree and 2 tree, and of course because $u$ and $v$ are connected by an edge in graph $G$, the colors should be different.


texts: Is $(aaaaa)^n aa (aaaaa)^n$ a regular language?

texts: Is the language $\lbrace (aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N} \rbrace$ regular? It looks like I need infinitely many states so it is not regular.


texts: Enumerating pairs of disconnected cliques in a graph

texts:
Given an unweighted graph $G = (V,E)$. I am interested in enumerating all pairs of disconnected cliques, i.e. there should not exist any edge between two cliques. (For example, there would not exist any such pair in a complete graph). A clique could be of any size $\geq 1$.

Are there any standard approaches to solve this problem? If so, could someone please highlight the sources or suggest some approaches?


texts: Is Half - Palindrome subset of a context-free language context-free?

texts: Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a DFA. Is it possible to create a PDA here as well? I am stuck on this or even if there is a counter example?


texts: Time complexity of a precedence constrained selection problem

texts:
I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem)

[Assuming operations on integers take O(1) time]

We are given a set $N$ of $n$ items, that are subject to general precedence constraints (a partial order $E$ on $N$). The problem could then be represented by an acyclic directed graph $G(N,E)$ where the nodes represent items and edges represent precedence constraints. Each item has a selection cost $c_i$ that may be positive, zero, or negative. The objective is to find a subset $S \subseteq N$ of items that is precedence feasible, i.e., $\forall i \in S:\{j \in N|(j,i) \in E\}\subset S$, and minimizes the total selection cost $F(S)=\sum_{i \in S}c_i$.

I tried to find a reduction from CLIQUE or 3-Dimensional Matching, but I couldn't.

Thank you in advance :)


texts:
My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same time?

Consider a graph on two vertices "u" and "v" and assume that it is strongly connected as well as a DAG. A path from u to v exists as well as a path from v to u which creates a cycle. No?


texts: Using humans as components to build a computer?

texts:
Ok before I start I realise this is on the fringe of on-topic (I have read the Questions help for this site), particularly as this is not a real-world problem. However:

I cannot find anything relevant on Google
From a purist point of view surely it must fall within Computer Science?

In any case, if I have overstepped a boundary then I apologise and welcome the  Closure as I am an avid user of other SE sites so I understand the issues.

Caveats aside, here it is:
I have long wondered if it would be possible to build a functioning computing system, using humans as discrete logic components, to solve problems that individual humans could not solve in a practical timesscale. For example, imagine a number of humans stranded on an island without any machines, that needed to crunch some complex numbers to escape.

I imagine arranging people so that they receive inputs from other groups within the system, make simple decisions (perhaps binary decisions, perhaps not) and pass the outputs to other groups.

Then I imagine some kind of programming language could be developed to control the data and computation flow and the language could be used to solve complex problems without individuals understanding the overall problem.

So I guess the above is not an answerable question- but does anyone know of any research, books, papers or whatever on what it would take to achieve, what kinds of of problems could be addressed and potentially solved, what kind of control language could be deployed and how the architecture could be scaled up to handled more complex problems?

I suppose, in essence, I am looking for anything on "idealised" atomic (as in self contained) and standard computing units that could be arranged at will- I am just thinking in human terms.

I find the idea fascinating and alluring. I'd love to try it out one day and see what performance could be achieved! Sorry for the tags I have used, as I was searching the tags here I quickly became aware I have no idea of the correct terminology for what I am thinking, though I am sure it exists within the field...


texts: How to find maximum matching edges in undirected tree

texts:
Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.

My approach:

Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

Pseudo code:

graph = {
     1: [2, 3],
     2: [1, 4, 5],
     3: [1, 6],
     4: [2, 7, 8],
     5: [2, 9],
     6: [3],
     7: [4, 10, 11],
     8: [4, 12, 13],
     9: [5],
    10: [7, 14],
    11: [7],
    12: [8],
    13: [8, 15, 16],
    14: [10],
    15: [13],
    16: [13],
}
# example graph I used for testing purposes

while we haven't seen all nodes:
    leaves = [i for i in graph if len(graph[i]) == 1]
    seen += leaves
    for leaf in leaves:
        parent = graph[leaf][0]
        del graph[leaf]  # Throw away all leaves
        if not parent in seen:
            del graph[parent] # And throw away their parent
            matching_edges += [(leaf, parent)]
            seen += [parent]
            next_round_nodes += [parent]

But I'm afraid that is not linear, is it?
Because first we look at $|V|$ and perform our algo. Then we do the same with $|V|-c$ leaves, where $c$ could actually be 2, if I understand that correctly, looking at graph which is a "line". So, really that seems quadratic.

TL;DR:

Is my algorithm correct?
What is the runtime?
If it is not linear, what other approach could I chose?


texts: Differentiate arguments in SPASS prover formula

texts:
I have a formula in FOL:
$\forall x \exists y: B(x) \implies C(y)$
and in SPASS: forall([X], exists[Y], implies(B(X),C(Y)))

I want to check the formula: $\exists x: B(X) \implies C(X)$ and in SPASS exists([X], implies(B(X), C(X)))

The problem is I want to determine that X and Y are different (like in my first formula) and I want to be the second formula false because of the fact, that B and C are for the same X: $B(X) => C(X)$ but my first formula said that it should be different.

Is there a way to tell SPASS that these arguments should be different?


texts: Transform a set of points to have a minimum distance between them

texts: Assume I have a set of $N$ ordered points, $X$. I would like to find the set of $N$ points, $Y$, where the distance between $X$ and $Y$ $(d = \sum_{i=0}^{N-1} |X_i - Y_i| )$ is minimized but there is a minimum distance between points of $M$ $(Y_{i+1} - Y_i > M)$. Is there an algorithm or approach to deriving $Y$ given $X$ and $M$?


texts: Understanding Dinic's algorithm using dynamic trees

texts:
I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan algorithm).

I just wish I could find an image source or video that can help me visualize the steps. Something like this is really close. But I just really want to find thing to lead me step by step in a visual way or a way that doesn't involve pseudocode.


texts: If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?

texts: Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-complete or more powerful than turing-complete, or is it possible for X to be less powerful than a turing machine?


texts:
How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality?

There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough road.
Taking this into account, if there are roads $p1$: the short distance with road quality $3$ and $p2$: the long distance with quality $1$, the longer path $p2$ is chosen due to easier road difficulty.

The quality of the road is more important than the distance. If there are roads of equal quality the shorter one is chosen.


texts: Remapping values to bias a uniform set towards a certain curvature

texts:
I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices.

I came up with this:

function curve_map(curve) {
    //  convert to sorted points
    var points = [];
    for (var x in curve) { var y = Number(curve[x]);
        points.push( {'x' : Number(x), 'y' : y} );
    }
    points.sort(function(a,b) {return a.x - b.x});

    //  create segments
    this.segments = [];
    var posy = 0;
    for (var i = 1; i < points.length; i++) {
        var n = points[i].y + points[i - 1].y;
        var seg = {
            'x0' : points[i - 1].x,     'x1' : points[i].x,
            'y0' : points[i - 1].y,     'y1' : points[i].y,
            'n0' : posy,                'n1' : posy + n
        };
        posy = seg.n1;
        this.segments.push(seg);
    }

    //  normalize n
    for (var i = 0; i < this.segments.length; i++) {
        this.segments[i].n0 /= posy;
        this.segments[i].n1 /= posy;
        this.segments[i].nr = this.segments[i].n1 - this.segments[i].n0;
    }

    //  func
    this.apply = function(x) {
        for (var i = 0; i < this.segments.length; i++) {
            var seg = this.segments[i];
            if (x >= seg.n0 && x <= seg.n1) {
                var along = (x - seg.n0) / seg.nr;
                //along = seg.y0 / (seg.y1 - seg.y0);

                var val = seg.x0 + (seg.x1 - seg.x0) * along;
                return val;
            }
        }
    }.bind(this);
}

What this does is

take 2 points and make a segment, preserving the original coordinates
each segment's length is equal to the sum of Y of both points
after creating a segment between all the points, normalize so the chain of segments reaches from 0 to 1

So now I have a chain of segments. If I feed it a value, it looks up which segment it belongs to, checks how far along in the segment it is and remaps the location to the original interpolated x coordinates of the segment.

In theory I expected this to shave off the corners of the original curve since I don't know how to account for the difference in Y values in each segment.

Anyways, the result is quite different:

The red curve is what I fed the "curve_map" and what it should mimic

The black one is ~10k uniformly distributed random values put through the algorithm.

At least it sorta follows the line... but this is nowhere near good enough. Also I'm out of ideas on how to fix it.

Does anybody know if what I'm trying to do actually has a name? So I could read up on it or maybe find a neat algorithm to port..


texts: For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases

texts:
Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let

  g() { f(v) }

be the function with no argument which just calles $f$ with $v$ as an argument. Then we need $n + |v| + C$ bits to store it, where $C$ is some constant which takes account of the additional bits needed to declare $g$, and this is independent of $v$ and $f$.

So in any programming language so far, to go from programs accepting parameters, to the one for a fixed parameter the desriptional complexity  raises up at most by a fixed constant plus the descriptional length of $v$.

Does the same hold for Turing-machines? If I have a Turing-Machine which for input $x$ produces $y$, then to have a machine without accepting parameter to produce $y$ I can built one that first writes $x$ and then runs $M$, and a general machine that writes $x$ for any $x$ would be one that saves the tokens of $x$ in its states and writes them one after another. If I look at how instructions are specified in Turing machines, then we see that for $x$ we need $|x|\cdot C$ bits (with $C > 1$) then to store this additional machine, hence given $M$ with $M(x) = y$ we get a machine $M_x = y$ without arguments with
$$
 |M| + C|x| + C'
$$
needed bits, where $C > 1$ and $C'$ account for some additional setup independent of $M$ and $x$.

But would it be possible to built a Turing machine $M_x$ with $M_x = y$ without input which has descriptional complexity at most $|M| + |x| + C'$ for some constant $C'$ independent of $M$ and $x$? Like above for ordinary programming languages?


texts: Complex property of sparse horner polynomials by induction

texts:
I'm following this article to do a formal proof on elliptic curve cryptography. My question here addresses only a property "easily proved by induction".

Definitions (the important part is the addition definition at the bottom)

Let assume the following hierarchy:

abstract class shf;
case class const(c: Integer) extends shf
case class POP(i: nat, p: shf) extends shf
case class POW(i: nat, p: shf, q: shf) extends shf

where nat is the type for naturals including zero. We state also a property on the hierarchy called normality given by the function:

def normal(p: shf) = p match {
 case const(c) => true
 case POP(i,p) => i > 0 && normal(p) && p = POW(_,_,_)
 case POW(i,p,q) => i > 0 && normal(p) && normal(q) && p != POW(_,_,0)
}

Assume we have some type shfn to say that we have a shf with the normality property. Then also define these functions:

def pop(i: nat, p: shfn) = {
 case i = 0 or p = const(_) => p
 case p = POP(j,q) => POP(i+j,q)
 case _ => POP(i,p)
}

Denote nat* the naturals without zero:

def pow(i: nat*, p: shfn) = {
 case p = 0 => pop(1,q)
 case p = POW(j,r,0) => POW(i+j,r,q)
 case _ => POW(i,p,q)
}

Finally, define the addition operation:

if (x = const(c1)) {
 if(y = const(c2))       c1+c2 (over the integers)
 else if(y = POP(i,p))   POP(i,x+p)
 else if(y = POW(i,p,q)) POW(i,p,x+q)
}

if(y = const(c)) y+x

if(x = POP(i,p) && y = POP(j,q)){
 if(i=j)        pop(i,p+q)
 else if(i > j) pop(j,POP(i-j,p)+q)
 else if(i < j) pop(j,POP(j-i,q)+p)
}

if(x = POP(i,p) && y = POW(j,q,r)){
 if(i=1) POW(j,q,r+p)
 else    POW(j,q,r+POP(i-1,p))
}

if(y = POP(i,p) && x = POW(j,q,r)) y+x

if(x = POW(i,p,q) && y = POW(j,r,s)){
 if(i=j)        pow(i,p+r,q+s)
 else if(i > j) pow(j,POW(i-j,p,0)+r,q+s)
 else           pow(i,POW(j-i,r,0)+p,s+q)
}

The problem

I'm trying to prove that if $x,y$ are normal then $x+y$ is also normal. But the induction is not trivial to me.

I tried to split it. First I consider $x$ to be constant and everything went well by using the corresponding induction hypothesis.

The problem appears when I consider $x$ to be $POP$ and I do induction on $y$. When $y$ is also $POP$ I have to rely on the $POW$ case because note that as $x,y$ are normal and instances of $POP$ then their second components need to be instances of pow. The other cases for this situation then need the $POP-POW$ case. But proving the $POP-POW$ case could potentially lead to a $POP-POP$ case again.

How can I structure my proof to succeed?

You may want to look at the actual proof on ACL2 here. Also, if you have any ideas to simplify the problem (to make it more easy to reason about and describe it) please let me know.

Intuition

Intuitively a POP construct represents a jump in the list of variables where our shf form is evaluated and a POW represents a polynomial in current variable x of the form $x^i \cdot p + q$. So normality for POP means that the jumping index is as big as possible (there cannot be nested POPs) and normality for POW means the power index $i$ is as big as possible.


texts: Proving that directed graph diagnosis is NP-hard

texts:
I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and constructing a reduction from that problem to the following problem I'll call DGD (directed graph diagnosis).
Problem

An instance of DGD $(V,E,k)$ consist of vertices $V = I \overset{.}{\cup} O \overset{.}{\cup} B$, directed edges $E$ and a positive integer $k$. There are three types of vertices: vertices with only incoming edges $I$, vertices with only outgoing edges $O$ and vertices with both incoming and outgoing edges $B$. Let furthermore $D=O\times I$.
Now, the problem is whether we can cover all nodes with at most $k$ elements of $D$, i.e.
$\qquad \displaystyle \exists\,S\subseteq D, |S|\leq k.\ \forall\, v\in V.\ \exists\,(v_1,v_2) \in S.\ v_1 \to^* v \to^* v_2 $
where $a\to^* b$ means that there is a directed path from $a$ to $b$.

I think that the Dominating Set problem is the one I should be reducing from, because this too is concerned about covering a subset of nodes with another subset. I tried creating a DGD instance by first creating two nodes for each element of the dominating set, copying all edges, and then setting the $k$ of the DGD instance equal to that of the DS instance.
Suppose a simple DS-instance with nodes $1$, $2$ and $3$ and edges $(1,2)$ and $(1,3)$. This is a yes-instance with $k = 1$; the dominating set in this case consists of only node $1$. Reducing with the method just described, this would lead to a DGD instance with two paths $(1 \to 2 \to 1')$ and $(1 \to 3 \to 1')$; to cover all nodes, just one pair $(1, 1')$ would be sufficient. This would have worked perfectly, were it not for the fact that the dominating set of the DS-instance cannot, of course, be determined in polynomial time, which is a requirement here.
I have found that there are many good-looking ways to transform the edges and vertices when reducing, but my problem is somehow expressing DGD's $k$ in terms of DS's $k$. Dominating Set seemed a fitting problem to reduce from, but because of this I think that maybe I should try to reduce from a problem that has no such $k$?


texts:
I am currently learning about Turing Machines, I am curious if a Turing Machine can have fewer states ?  Can it be done like a Transition Graph where you can have multiple states at once ?

I got this TM off of a youtube video sorry for bad hand writing, but could I just merge some of the states like you would do in Transition Graph, so instead of having 5 states it would have 4 states ? TM are more advanced so I don't know if you are even able to do this...thanks!

how could I make this into 4 states TM instead of 5 states ? in TG if would take 5 seconds do it...


texts: How is type safety handled differently between reference and value types?

texts:
I'm trying to understand how type safety is preserved for value types and for reference types, specifically in languages with managed memory (such as C#).  I understand that reference types (i.e. classes) have data allocated onto a managed heap, with a reference to that data allocated on the stack.  Is there metadata about the type of the data passed around with the pointer?  Is there a new 'pointer type' created along with the class itself?

I've been looking at this SO question and this blog post but neither discuss typing itself as it relates to these topics.


texts: Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1

texts:
I'm doing an online course in which I'm struggling with the following (multiple-choice) question:

Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's length is either $-1,0,$ or $1$. Suppose further that $G$ is strongly connected, with at least one $u$-$v$ path for every pair $u,v$ of vertices. The graph $G$ may or may not have a negative-cost cycle. How large can the final entries $A[i,j,n]$ be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual, $n$ denotes $|V|$.) [WARNING: for this question, make sure you refer to the implementation of the Floyd-Warshall algorithm given in lecture, rather than to some alternative source.]

$+\infty$

$n^2$

$2^n$

$n-1$

I'm furthermore told that $n-1$ shouldn't be selected, with the hint "Experiment with graphs that have negative-cost cycles".
Here is the Floyd-Warshall algorithm as described in the lectures:

Let $A$ be a 3-D array, indexed by $i,j,k$.
Define the base cases:
$$ A[i,j,0] = \begin{cases}0 & i = j \\ c_{i,j} & (i,j)\in E \\ +\infty & \text{else}\end{cases}$$
For k = 1 to n
    For i = 1 to n
        For j = 1 to n
            A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1])

Correctness: From optimal substructure and induction, as usual.
Running time: $O(1)$ per sub-problem, $O(n^3)$ total.

In the course's nomenclature, $n$ denotes the total number of vertices in the graph, so $A(i, j, n)$ is the shortest path from node $i$ to $j$ which may use all $n$ nodes.
As I understand it, a shortest path between any two nodes has at most $n - 1$ edges, so if the maximum cost of an edge is 1, I would expect the maximum cost of a shortest path to be $n - 1$. I don't see how the presence of negative-cost cycles could change this?


texts: Looking for an algorithm to generate an identicon/avatar from genome data

texts:
I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form.

Identicons are essentially a visual hash of of data. usually string data such as an IP address or name. In this case, rather than generating an identicon from a single piece of string data. I want to use the entirety of the genotype information (the 4th column) to summarize this data into a graphical representation as a way to visually identify someone from their partial genome.

The input file is a tab-separated file consisting of 600,000 rows. Each row contains the chromosome identifier (There are 23 in total: 1-20, X, Y or MT), the position of the single nucleotide polymorphism (SNP) and the genotype (a two character variation of G,A,T or C). Below is a two line excerpt from the file.

#RSID        Chromosome   Position  Genotype
rs7537756       1         854250    AG
rs13302982      1         861808    GG

Using the Chromasome, Position and Genotype columns. I would like to generate an abstract identifying image from this data. Since there is far too much data, this image does not need to capture the data, only summarize it in a visual fashion. The goal is to setup a service that analyzes anyone's genome file and generates an identicon that is unique to them.

For more information on identicons See the wiki page


texts:
I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me.

Is there any practical (or impractical for that matter) applications of knowing the automorphism group of a graph?


texts: Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?

texts:
Given a DFA (D1) with P1 states, that accepts a language L1.

Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a palindrome (of maximum length P1).

How many states would the minimized D2 have (worst case)? And time complexity?

Similarly, NFA (N1) with Q1 states that accepts a Language L3. How many states would minimized (N2) have (worst case)? Along with its time complexity?

The generic Palindrome Language is non-Regular hence a DFA/NFA for it is impossible but I am unaware of the limited Palindrome case in DFA/NFA?


texts: Finding shortest and longest paths between two vertices in a DAG

texts:
Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time?  Path lengths are measured by the number of edges.

I am interested in finding the range of possible path lengths in polynomial time.

Ps., this question is a duplicate of the StackOverflow question Longest path in a DAG.


texts:
While I am learning a lot from others here at the Computer Science site, I must admit that I don't get as much out of some questions and answers since I typically don't understand the theorems to the level necessary. I am currently reading How To Prove It - A Structured Approach which is starting to make the theorems easier to read, but still does not get me to the point of being able to understand the theorems to the point that they add great insight to the question or answer.

For this question Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

there is a use of a peroid in the premise.

  $\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

What does the period mean? I would be expecting either a comma to mean conjuction or or to mean disjunction, but not a period. I don't see how this could be converted to logical statements.

Note: Jukka Suomela has already provided the answer in this CS meta question.


texts:
I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient programmer, but I know I would be a lot better If I was more confident in my ability  to swim on a lower level of the stack. I hardly know any C. (The syntax is easy, but I've never actually implemented anything in it besides some 100 level HW problems. I see this as a problem because so much is written in C.)

I want to be:

better at discrete math
More versed in algorithms
Have a more intimate understanding of how the higher level tools that I rely on actually work.

Basically, I know how to use logic, but I have become dependent on high level tools and I don't like that.

I also suck at math. I mean I understand it conceptually, and Im comfortable with set theory, so, Python's data structures are really all I need, but I want to be better at algorithms and math is necessary for that.

Are there any websites or other resources that stress an approach like this.


texts: Regular expression for string with substring 010 and ending with 01

texts:
How can one design a regular expression for given string in title ?

Also how can we draw DFA of that regular expression?

I've tried many expressions but couldn't succeed, please help.


texts: Partitioning vertices in a bipartite graph according to minimum vertex covers

texts:
How to solve this problem?

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.
Consider a set of all minimum vertex covers of a given bipartite graph. Your task is to divide all vertices of the graph into three sets. A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex. A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph. If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).


texts: Why is an Artificial Neural Network with high accuracy score giving poor results?

texts:
I implemented my ANN using SKlearn module's class MLPClassifier. Fitting it on some data and testing it on a very specific subset of said training data, it gives a score of 1.0, but actually using the ANN to generate outputs for said testing data almost always gives incorrect output. What could be the possible reasons for this?
I am using this ANN as a memory network and there is never a case when input is out of training data.


texts:
An optimisation problem requires minimising some function $f(x)$, where $x$ is a
vector of integers. What is the corresponding decision version of the problem?


texts: General object recognition versus specific object recognition

texts:
I have a question about the difference between general object detectors and specific object detectors.

By specific object detectors, I'm referring to classifiers/object recognizers that are built to recognize a single object, eg. a person, or a vehicle.

By general object detectors, I am referring to algorithms which are trained on a number of different objects (and are therefore able to differentiate between a car, house, person, and banana). Importantly, I am referring here to algorithms that are inherently designed to accommodate many object classes, not merely collections of several specific object detectors put together.

I have an assumption, which is that:
Specific object detectors, which are used to recognize a specific object such as a vehicle, are generally more accurate/precise, than the results to be expected from a general object detector which is being used to recognize that same vehicle, given the same amount of space and time.. The reason is that given limitations on space and time, there is only so much that an algorithm can capture. So using a specific object detector for vehicles would be more accurate since the time and space used by the algorithm's training and testing is specialized on vehicles only and is better at this task.... rather than using a general object detector for recognizing those same vehicles.

Put briefly:

  "With an increase in the number of objects to recognize, the complexity of models
  increases, and in accommodating for that, the reduction in accuracy of
  detection for each individual object also increases."

I've looked for evidence of this assumption but haven't found any yet.
And is this assumption true? Is there any evidence to back up whether or not it's true?


texts: Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

texts:
One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 in CLRS 3rd edition page 122 where by acting randomly we manage to impose a distribution on our inputs).

With Simple Uniform Hashing (SUHA) we have that the hash function "evenly distributes" the keys in a random fashion across the hash table. This way the average length of a chain is not too long. Is the randomness that we assume inherently exists in this magic hash function the way we battle worst-case inputs? i.e., is this exactly how we ensure that the expected runtime will be small, since  our hash function is random and no series of keys is bad? (i.e., a worst case input doesn't exist because the hash function will act randomly and hence, make the expected chain lengths small).

I am not sure if this is right or if this is the right way to think about it, but that's how I think of hash tables, that they are random so no chain can get too long (usually) and hence we perform well.


texts: Examples for incomparable semi-decidable but undecidable languages

texts:
In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made:

  'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, computably enumerable sets that are not Turing equivalent to the halting problem. In particular the answer is yes if there are two computably enumerable languages $A$ and $B$ that are incomparable with respect to $\leq_T$, i.e. such that $A\nleq_T B$ and $B\nleq_T A$.

The text goes on proving that there exists such languages $A$ and $B$.

Does this imply undecidable recursively enumerable sets are not isomorphic to the halting problem? Are there examples of such languages?


texts: API to retrieve answers for general questions

texts:
I was looking for a service (with API) where I can ask it a general question (aka, when was Einstein born?) and retrieve an answer from the Web.

Is there any available service to do that? Have tried Watson services but didn't work as expected.

Thanks,


texts:
In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine.

In his paper "Actor Model of Computation: Scalable Robust Information Systems" Carl Hewitt proposes following hypothesis:

  All physically possible computation can be directly
  implemented using Actors.

He comments that this hypothesis is an update to Church-Turing thesis that all physically computable functions can be implemented using the lambda calculus (or TM), stating that:

  It is a consequence of the Actor Model that there are some computations that cannot be implemented in the lambda calculus.

Then he recalls Plotkin's informal proof of NTM to have property of bounded nondeterminism:

  Now the set of initial segments of execution sequences of a given
  nondeterministic program P, starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite. That is, the tree is finitary. Now König's lemma says that if every branch of a finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of P terminates, then there are only finitely many execution sequences. So if an output set of P is infinite, it must contain a nonterminating computation.

Then he presents algorithm in Actor Model semantics which seem to have property of unbound nondeterminism, stating that the later proves the hypothesis above.

The algorithm is a computation of integer value. For NTM it is stated this way:

Step 1: Either print 1 on the next square of tape or execute Step 3.

Step 2: Execute Step 1.

Step 3: Halt

It's properties are: if NTM halts, there are only finite number of states which it can be in (bounded nonndeterminism, as shown by Plotkin); and it may never halt whatsoever (it has a subtree of computation of infinite depth).

For Actor Model it is stated like this:

Create an Actor which can receive two messages: 'go' (makes it increment counter and send itself another 'go' message) and 'halt' (makes it return counter value).
Send this actor 'go' and 'halt' messages.

Since Actor Model semantics state that a message is guaranteed to be delivered and there is no restriction on when will it be delivered, then if actor halts, there are infinite possible states in which it can be (unbounded nondeterminism); however, it will halt always.

However, it really doesn't seem to me to imply the hypothesis stated and it seems highly unlikely that we can actually achieve Actor Model semantics on a real hardware.

I'd like to propose following questions:

Does the property of unbounded nondeterminism really has to do something with computational power? Is 'computing an unbounded integer' algorithm really impossible to implement on any TM?
If so, what is the class of computations that requires it?
Edsger Dijkstra argued that is is impossible to implement system with unbounded nondeterminism; Tony Hoare agreed that the implementation should try to be reasonably fair. Is level of fairness achievable today is good enough to say that we can actually have computations which require this property implemented on physical hardware?
If we add an entropy source to NTM (or PTM) in form of fair random number generator, can we achieve the same unbounded nondeterminism property as in the Actor Model?


texts: Describing the language formed by a particular grammar

texts:
G → G B ⏐ G N ⏐ ε
B  → ( E )
E  → E ( E ) ⏐ ε
N  → ( L ]
L  → L E ⏐ L (⏐ ε

For this grammar, the prompt asks to describe in  the language that this grammar describes and builds.

I got to the point of first trying at defining the language each one builds but the recursiveness of this grammar threw me off a bit.

I'm kind of stuck, thus far I tried to start with let's say N and try to describe it as generating a left paren followed by a left paren and right bracket.

I could really use some direction on where to go with this.


texts: Hardware thread context and register renaming

texts:
I'm having some issues understanding what happens on a context switch with the physical register file in an out-of-order CPU that implements context switching. Suppose that a CPU consists of 4 hardware thread contexts and that the ISA consists of 32 architectural registers. Does the physical register file get overwritten when a context switch occurs, or do the 4 hardware thread contexts compete on the use of physical registers, for faster context switches (because they don't need to be overwritten)?

More concrete: "Does a CPU with 4 hardware thread contexts and an ISA consisting of 32 architectural registers and 96 physical registers in total make sense?"


texts: Efficient simulation of an NFA, while preserving the paths to the accept states

texts:
The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.

However, for my purpose I need to know which paths the NFA went through for accepted words. This is obviously not trivial if I simply use the subset construction method. The NFA could also have $\epsilon$ transitions.

Of course, any such simulation could have a bad worst-case, in which there are a humongous amount of ways that the automaton could accept a given word. However, it'd be nice to have some sort of algorithm that runs, in, say, $O(m+n)$ for a word of length $m$ that the NFA has $n$ ways of accepting.

Is there any efficient way to do this?


texts: Is decimal number 8 represented as 3 bits or 4 bits in computer?

texts:
I was told by my professor that

"It takes c * ln(n) bits to store a number n, where ln() is base 2 and c is a constant."

Thus, to store a number 8, we need ln(8) = 3 bits(I think const c can be ignored here.), but isn't 8 stored as "1000" in a computer, which is 4 bits?

Thanks.


texts:
Given two sets A and B of sizes |A| = n and |B| = m, where m >= n.
There are edges from set A to set B.
I need to find the number of matchings where all of vertices in set A have been matched with one vertex in set B.
Is it possible to caclulate this quantity ?

(I have very little knowledge of Graph Thory and Bipartite Matching or how it is computed)


texts: simple lower bound for constructing a Spanning tree

texts: i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts the algorithm} the problems of constructing a spanning tree takes at least $\Omega(m)$ messages, where $m=|E|$


texts: Are there any optimization problems in P whose decision version is hard?

texts: Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any optimization problem which is easy but its decision version is hard?


texts:
So let's say I have a 4x4 image with 3 channels. So we have 3 4x4 matrices where each matrix represents a channel. Now let's say I also have a 3x3 kernel. I know that for convolution layers, I have to slide the kernel over the image and take the dot product. So for two 3x3 matrices, would I perform matrix multiplication and take the sum and do I need to perform this convolution for each image and then add them together?

For my example, if the images were

4, 23, 1, 0
3, 0, 10, 2
3, 71, 8, 2
3, 5, 16, 7

1, 15, 6, 1
6, 1, 6, 4
10, 21, 2, 1
7, 2, 4, 3

7, 4, 0, 1
3, 0, 10, 14
6, 7, 6, 3
5, 1, 6, 9

and the kernel was

1, 17, 9
10, 3, 6
13, 4, 2

then what would be the output values?


texts: Complexity Measure and Practical Hardness of SAT

texts: I am study this paper "Relating Proof Complexity Measures and Practical Hardness of SAT". Here the authors propose to use pebble formulas to find a relation between these and practical SAT performances using as measure the space of resolution. My question is is it to possible to extend that relation beyond of pebble formulas? For example for a random CNF formula.