All Questions
48,914
questions
0
votes
0
answers
6
views
How to show that $M$ is not finitely axiomatizable in the following case?
Problem: A set of formulas $M_0$ is an axiom system for a set of formulas $M$ if $\{A |A \text{ is a model for }M_0\} = \{A |A \text{ is a model for }M\}$, where $A$ is an assignment, or valuation. $M$...
- 35
0
votes
0
answers
5
views
Counting number of assignments restricted by implications
Suppose we have $n$ boolean variables, $x_1, \dots, x_n$. Some boolean variables can have implication relationships, e.g. $x_2 \implies x_5$, which means that if $x_2$ is true $x_5$ must also be true. ...
- 13.8k
1
vote
0
answers
25
views
Polynomial time algorithms for graphs and cycles
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
- 11
0
votes
0
answers
10
views
Livout analysis of control flow graph of a program
I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc ...
- 101
2
votes
3
answers
1k
views
Do programs within which a computable function runs a random number of times always halt, as in the halting problem?
I need some clarification regarding if computer scientists say a program like:
...
- 129
2
votes
1
answer
51
views
How to prove a problem is EXP hard
Summary of the problem: Given an alternating time turing machine ($M$), a polynomial $p(.)$ and a string ($w$), is it EXPhard to find if $M$ accepts $w$ using not more than $p(|M|+|w|)$ space?
My ...
- 21
2
votes
1
answer
32
views
FSA for 'closure' of a language; how to represent?
Is my interpretation of this correct?
I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA.
In order to do so, would I draw a new edge from the ...
- 77
3
votes
1
answer
599
views
Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff
Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...
- 33
-1
votes
1
answer
35
views
Why is ot returning TRUE in first case and FALSE in the second?
I understand 0.3 does not have an accurate binary representation.
Suppose I run the following code:
Why is the answer "True" in the first case and "False" in the second? Shouldn't ...
- 99
0
votes
0
answers
13
views
What is the data management file system? [closed]
ILE C++ is a C++ compiler that is created by IBM .
The compiler has a function called “SRCFILE()” that is described by IBM like this :
“The name of the file that you reference on the #include ...
1
vote
1
answer
44
views
Non-deterministic TM with an oracle to $R$
Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$.
I'd ...
- 356
2
votes
2
answers
59
views
Is there an NP-hard problem that becomes polynomial when the inputs are at most $2^n$?
Let Q be a computational problem that accepts as input some $n$ non-negative integers. Is it possible (assuming $P\neq NP$) that Q is NP-hard in general, but can be solved in polynomial time when ...
- 6,132
0
votes
0
answers
11
views
Calculating the most influential set of source nodes on a target node when a source node's signal is propagated
I am mainly posting for guidance, as I don't know where to start looking in order to solve the following problem:
Given a directed graph G with edge weights between 0 and 1. As well as a set of ...
- 1
2
votes
1
answer
39
views
Stuck reading "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums"
I am reading the paper titled "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums", and I am stuck on theorem 2.1, I believe it is wrong, the proof has a wrong ...
- 83
1
vote
0
answers
20
views
Equivalence of two approaches for sparsity
I am trying to understand whether the following two ways to achieve a sparse matrix are equivalent in Pytorch. Let me add some context:
I am training Sparse Neural Networks with a specific structured ...
- 111