All Questions

0
votes
0answers
13 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
2
votes
1answer
17 views

Help with figuring out if MAX(L) is a CF language

We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as: $MAX(L)$ = {$w_1 \in L $|...
2
votes
1answer
28 views

Number of equivalence classes in $P$

I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...
2
votes
1answer
117 views

Showing that a language is NP Complete (advice)

I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, ...
1
vote
1answer
16 views

Complexity and hardness of undirected path

Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$...
3
votes
2answers
31 views

How do you prove a heuristic is admissible?

How does one prove that a suggested heuristic is admissible? Is this even possible? For Example: Let's say I have the game Free Cell. Rules: https://en.wikipedia.org/wiki/FreeCell How can I ...
-1
votes
0answers
17 views

How to precisely know whether a language is regular ? , a regular expression can be generated for it ? , as well as dfa? [duplicate]

I feel difficulty in finding whether a language is regular and also is regular expression can be generated ?? Please anyone let me know about all the possible cases. This will help me very much..
1
vote
1answer
31 views

calculating a shortest path in a table structure that changes in real time

I have a table that looks like this In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user. In any moment the player ...
1
vote
1answer
62 views

Are all compilers Turing Machines?

So the definition of a compiler I got is that: A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No". So does that mean all compilers ...
0
votes
0answers
26 views

Why can't we generate the output of a cellular automata at time step t without first generating all the preceding states

Why can't we generate the output of cellular automata at time step t without first generating all the preceding states? Why can we do this for some functions? What features of a function does it ...
1
vote
1answer
42 views

Given n standard C++ STL maps, can I merge them? [on hold]

I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick. For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}} Then the ...
1
vote
0answers
30 views

Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
1
vote
0answers
14 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
0
votes
0answers
20 views

$NTime(2^n) \subseteq NSpace(n^k)$ implies $EXP = PSPACE$?

Assume $NTime(2^n) \subseteq NSpace(n^k)$, for some fixed $k$. Is it possible to imply that $EXP = PSPACE$? and what about $NEXP = PSPACE$? It seems the answer might be YES, because this question ...
1
vote
1answer
37 views

Can the difference of a non-regular and a regular language be regular?

I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises: If $L_2,L_3$...
1
vote
2answers
28 views

What is the graphic TSP?

I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP : ...graph-TSP, that is, the traveling salesman problem where distances ...
3
votes
0answers
38 views

Iterating over a union of sets denoted by bitmasks

Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$. Such bitmask denotes a set $S \subset \mathbb{B}^...
1
vote
1answer
22 views

Complexity of “half cycle”

I'm working on the following problem: HALFCYCLE (HALFC): Input: A directed graph $G = (V,E)$. Output: Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$. Prove that if $\...
0
votes
1answer
29 views

String matching and bioinformatics [on hold]

I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.
1
vote
1answer
64 views

Is “Query Equivalence” decidable?

I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d ...
2
votes
1answer
48 views

Thought process for the following problem?

We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or ...
1
vote
0answers
26 views

Substituting a term for a variable in a context

At this link you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.) On slide 10, he gives a standard ...
0
votes
1answer
8 views
0
votes
0answers
25 views

Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements: (i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$ (ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$ For the Space ...
1
vote
0answers
19 views

Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...
-1
votes
0answers
8 views

Apache server runs only in debugging mode [closed]

I have a code base in Java and I am using Intellij Ultimate edition. When I run the server normally, it fails and gives exception due to TimeoutException. When I run the server in debug-mode and place ...
2
votes
1answer
26 views

One-taped RAM vs Multi-taped RAM

In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently. (Well, actually I'm not ...
-1
votes
0answers
17 views

Operator Precedence Parsing

In operator precedence parsing we have the rule that no production is allowed to have two adjacent non-terminals or an epsilon production. Hence, the production $S \to ab$ is allowed but not $S \to AB$...
4
votes
0answers
49 views
+50

What is the generating algorithm for the “komb” instances found on satcompetition.org?

For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT ...
0
votes
0answers
15 views

Go Back N question(netwrok)

Hello I am trying to understand the GBN protocol and I encountered the following question during my homework. Assume that we have GBN protocol with a window size of 20. The sender sends 15 packets ...
4
votes
1answer
100 views

Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: $$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
2
votes
0answers
20 views

Permutation to maximise strings' common prefix

Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix. Given a set $S=\{(s,w)\}$ of pairs of ...
1
vote
0answers
30 views

Is There A Difference Between Search And Optimization?

Is one a subset of the other? Two differentiable processes? The same thing? In the textbook "AI: A Modern Approach", the terms seem to be used interchangeably.
0
votes
0answers
12 views

Balanced $\epsilon$-separated partitioning by a hyperplane

Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
0
votes
1answer
21 views

Why does an extended transition function not work if the string does not result in a final state? [on hold]

If I am not wrong a string is only accepted by a finite automata if the string results in a final state. Why is that? With symbols we can transition into another non-final state, why is that not ...
0
votes
1answer
25 views

Prove Subset-Sum is NP-complete - Alternative reduction?

It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
2
votes
0answers
125 views
+100

How does a Turing machine with one tape read its input?

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
3
votes
1answer
40 views

How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or $O(n^{\log_b{a}} + f(n))$ Today I was faced with $T(n) = T(\sqrt n)...
3
votes
2answers
48 views

Proving a problem as NP-complete

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs ...
1
vote
0answers
13 views

Constraint headers format in CHR

I'm new to CHR and I was wondering if it makes sense to have have functions as arguments for constraint heads in a rule. I know that in the body of the rule this is possible. E.g. Is ...
2
votes
1answer
20 views

Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''

I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my ...
0
votes
0answers
21 views

Exponential search worst-case performance

I'm learning about Exponential search and I keep reading that the worst-case performance is $\log_2 i$ where $i$ is the searched index. I tried with an array containing $1073741824$ elements ($1024\...
3
votes
0answers
57 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
0
votes
1answer
21 views

Why does paging not have external fragmentation?

I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not ...
0
votes
1answer
68 views

Is computer science really a branch or sub-branch of physics? [closed]

Given that a computer is basically an electronic machine, is computer science really a branch of electronics, which is in turn a branch of physics?
0
votes
0answers
27 views

count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
0
votes
0answers
9 views

Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...
0
votes
1answer
42 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
-2
votes
0answers
8 views

3 sub part on Virtual Memory [on hold]

3 sub part on Virtual Memory. i need the solution as soon as possible please help me. thanks
1
vote
1answer
22 views

What are the best ways to find errors in a sequence of messages (strings)?

I am currently working on a thesis, where the main goal is to find errors (like a missing message, wrong sequence) in message sequences. The messages are distinguishable by their name, have further ...

15 30 50 per page