37 research outputs found
Equilibria for networks with malicious users
No full textWe consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behaviour. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to this cost. We define a generalized model, present characterizations of flows at Wardrop equilibria and prove bounds for the ratio of the social cost of a flow at Wardrop equilibrium over the cost when centralized coordination among users is allowed
On the Complexity of SAT
No full textWe show that non-deterministic time NT IME(n) is not contained in deterministic time n 2-# and poly-logarithmic space, for any # > 0. This implies that (infinitely often) satisfiability cannot be solved in time O(n 2-# ) and polylogarithmic space. A similar result is presented for uniform circuits. 1 Introduction Recently Fortnow [7] proved the first non-trivial timespace trade-off for satisfiability. His main result was that SAT is not computable in non-deterministic time n 1+o(1) and space n 1-# for any # > 0. Some consequences of his result are the following (for any # > 0): SAT ## NT ISP (n 1+o(1) , n 1-# ) SAT ## DT ISP (n 1+o(1) , n 1-# ) SAT ## NT IME(n log O(1) n) # NL In this work we use similar techniques as in [7] to prove a space-time lower bound result for non-deterministic polynomial time. We will show that if non-deterministic time NT IME(n) is a subset of deterministic timespace DT IME(n 2-# , polylog n) for any # > 0 then NT IME(t) # ..
Design Diagnosis Using Boolean Satisfiability
No full textRecent advances in Boolean satisfiability have made it an attractive engine for solving many digital VLSI design problems such as verification, model checking, optimization and test generation. Fault diagnosis and logic debugging have not been addressed by existing satisfiability-based solutions. This paper attempts to bridge this gap by proposing a satisfiability-based solution to these problems. The proposed formulation is intuitive and easy to implement. It shows that satisfiability captures significant problem characteristics and it offers different trade-offs. It also provides new opportunities for satisfiability-based diagnosis tools and diagnosis-specific satisfiability algorithms. Theory and experiments validate the claims and demonstrate its potential
Abstract Design Diagnosis Using Boolean Satisfiability ∗
No full textRecent advances in Boolean satisfiability have made it an attractive engine for solving many digital VLSI design problems such as verification, model checking, optimization and test generation. Fault diagnosis and logic debugging have not been addressed by existing satisfiability-based solutions. This paper attempts to bridge this gap by proposing a satisfiability-based solution to these problems. The proposed formulation is intuitive and easy to implement. It shows that satisfiability captures significant problem characteristics and it offers different trade-offs. It also provides new opportunities for satisfiability-based diagnosis tools and diagnosis-specific satisfiability algorithms. Theory and experiments validate the claims and demonstrate its potential.
