Problem Detail: The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = {u,v}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve Read More …
Category: Uncategorized
[Solved]: Product Matching problem in pattern matching
Problem Detail: The Product Matching problem is defined as follows: Input: Text T=t0,…,tn and pattern P=p0,…,pm over alphabet Σ=N . Output : All of the i places in the text where exists ci which holds ti+j = ci * pj for Read More …
[Solved]: Using natural deduction, show that: ∀x.(P (x) → Q(x)), ∃x.P (x) ⊢N ∃x.Q(x)
Problem Detail: How I would show: ∀x.(P (x) → Q(x)), ∃x.P (x) ⊢N ∃x.Q(x) using Natural Deduction? Would I not need to know what P(x) and Q(x) are to prove soundness and completeness? Asked By : JollyGr33nGiant Answered By : Andrej Bauer Read More …
[Solved]: Do we create a programming language by writing a compiler?
Problem Detail: Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, Read More …
[Solved]: What’s the meaning of the name P/poly?
Problem Detail: I understand the normal definitions of the P/poly class, but I’m curious how the name came about. The syntax of the name looks like a quotient group, but I can’t think of any way to define P/poly that would Read More …
[Solved]: Is $L = {a^jb^ia^{j-i}mid i,j ge 0 , j > i}$ context-free?
Problem Detail: I’m exercising for an upcoming exam and I find this exercise: Say whether or not the language $$L = {a^jb^ia^{j-i}mid i,j ge 0 , j > i}$$ is a context-free language. Justify your answer. I have already tried (using Read More …
[Solved]: $L$ APX-hard thus PTAS for $L$ implies $mathsf{P} = mathsf{NP}$
Problem Detail: If $L$ is an APX-hard language, doesn’t the existence of a PTAS for $L$ trivially imply $mathsf{P} = mathsf{NP}$? Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $mathsf{P} = Read More …
[Solved]: Significance of parameters in Tiny Mersenne Twister algorithm
Problem Detail: I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned integers “mat1”, “mat2”, “tmat”, Read More …
[Solved]: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
Problem Detail: I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting function: The Halt function takes an input a Read More …
[Solved]: How to cover maximum points with a fixed length line segment?
Problem Detail: The problem is defined as: Given a set of $N$ points $(x_1, x_2, x_3, ldots, x_n)$ and $L$ the fixed length of a segment. Find the number of maximum points which you can cover with a segment line of Read More …
