Tagged Questions
3
votes
0answers
50 views
How to find an expression whose value is 190
Given a set of numbers (in this case):
3, 7, 7, 100, 50
Either:
prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
2
votes
2answers
93 views
Number of ways to move 1 or more elements from one list to the previous list until one list remains
Given N elements, divided into at most N groups, which are then labeled 1 thru N, move all of the elements into the group labeled 1. By moving 1 to all of the elements, in group i to i-1. This means ...
2
votes
1answer
80 views
Oracle turing machine
I am learning computational complexity and this is a question of my assignment that I have issues trying to solve/understand.
An oracle Turing Machine M with oracle A is a Turing Machine with an ...
2
votes
1answer
72 views
Complement of NP-Complete
If a language L is NP-complete, with respect to polynomial time reducibility, does L ≤ co-L in polynomial time?
0
votes
0answers
88 views
How a direct method can be compared with an iterative method?
How a direct method can be compared with an iterative method?
I have an iterative method to compute Moore- penrose generalized inverse.
There are some direct methods available to compute Moore-Penrose ...
1
vote
1answer
65 views
Finding the computational complexity of an algorithm
Algorithm:
for (int i = 0; i < 2*n; i += 2)
for (int j = n; j >i; j--)
foo();
I want to find the number of times foo() is called.
...
0
votes
1answer
55 views
$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$
I must use O notation to show that:
$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$
But, I don't understand what mean: $n^{O(1)}$
1
vote
1answer
145 views
Structure and Formula encoding for Turing Machine
During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as
...
