# All Questions

46,364 questions
Filter by
Sorted by
Tagged with
10 views

### If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$

I have the problem If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$ To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
1 vote
15 views

### Deterministic infinite automaton equals a normal DFA?

Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA. Attempt ...
1 vote
18 views

### Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph

Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side. This is a conceptually simple problem, but I suspect it is ...
20 views

### Desgining NFA under certain constraints

I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
• 129
18 views

### How fixed point Decimal to Binary conversion algorithm works?

I'm reading a book which says that to transform a number from decimal to binary with fixed point representation you have to follow these steps: Take the integer part (the one before the point) of the ...
• 293
13 views

### Ford-Fulkerson algorithm running in pseudo-polynomial time

Consider a graph with $n$ nodes and $m = \mathcal{O}(n²)$ edges. The maximum capacity among all edges is denoted by $C$. The running time is given by: $\mathcal{O}(nmC)$ If I consider the input size ...
40 views

• 316
33 views

### How do you stop an algorithm at a specific run time?

so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my ...
• 101
28 views

### Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
• 301
1 vote
17 views

### Finding an approximate double-zero using binary search

Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by ...
• 5,818
11 views

### What is encryption and how is it used in protecting files?

What is encryption? How does it work to protect files? Please explain. Oh and how can I do that by myself???
1 vote
10 views

### Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
28 views

### Designing a DFA with nth character condition for any integer n

Let n be an integer. How can I write finite automata for the language L? L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}. (Please suggest answers; not hints.) Attempt Using Regex, I ...
14 views

### Uses of Hex and Octal numbers in programming

Where are these number patterns, Octal and Hex, being used? I read this but I want to know where they are used in programming.
24 views

### Workers with certain strength carrying boxes. (Greedy)

I just had an algorithms exam and had the following problem: Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s_i$ and each object has a weight $w_i$. Each worker needs to ...
1 vote
52 views

### As far as we know, what does GPT-4's training data look like?

I was asking ChatGPT local history questions, because I knew many of the answers and could test the robot. But lots of details were wrong and while it can write citations, it won't disclose its ...
• 111
19 views

### Prove that the problem MATCH is NP-complete

The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
31 views

### How do you deal with Skolem functions which escape their scope in elimination rules?

If you have an elimination rule for tuples which introduce the left and right pair into the type checking context, what do you do if the type of one of the elements is quantified and has been ...
28 views

### How to calculate the upper bound of the gredient of a multi layer ReLu neural network

Layers: We shall denote in the following the layer number by the upper script $\ell$. We have $\ell=0$ for the input layer, $\ell=1$ for the ﬁrst hidden layer, and $\ell=L$ for the output layer. The ...
38 views

### How do you write a logic function to determine if one 2s complement binary number is less than another?

Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example] It asks to ...
35 views

### Is there a maximal set of programs that terminate?

It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem: Is there a maximal decidable set of ...
1 vote
37 views

### Explanation of Cook-Levin Suitable for First Years

TLDR; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse I'm a prof. teaching first year algorithms+programming and want to give my students a taste of ...
• 11
32 views

### Parsing algorithms

I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It ...
1 vote
17 views

### Does adding a polynomial-time function impact APX-hardness?

I have two optimization problems $A$ and $B$, and I recently managed to show that there exist functions $f$ and $g$ that are computable in polynomial time, such that for any instance $x$ of $A$ there ...
• 11
24 views

### What is a practical example of a Context-Free Grammar?

I've been looking into Abstract Syntax Trees and came across the idea of a Context-Free Grammar which is described in the following way: In formal language theory, a context-free grammar (CFG) is a ...
• 99
1 vote
24 views

### Did Jon von Neumann know about Claude Shannon's work when he wrote the "First Draft of a Report on the EDVAC?"

In the "First Draft" JvN described an adder circuit to do binary addition, which was a much faster way of doing computer addition than using decimal lookup tables as the ENIAC had done. JvN'...
• 111
22 views

### Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits

I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$ We have $C|_V$ which is ...
38 views

### Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
• 7
25 views

### Upper bound of traveling salesman problem via dynamic programming

For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be \sum_{k=1}^{n-1} O\left(\left(\begin{...
• 101
30 views

### Function types in Computer Science Metanotation

See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF. I often make use of the BNF syntax observed there, as a substitute for ...
15 views

### Is proof based calculus more useful to become an AI researcher and an advanced specialist?

I don't know which single variable calculus course to choose: mit 18.01 or mit 18.014( proof-based calculus). I want to become an advanced specialist
48 views

11 views

### Confusion with Execution of NDFA

I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition): And ...

15 30 50 per page