The following is a partial transcript of the March 26, 2006, edition of "FOX News Sunday With Chris Wallace":

CHRIS WALLACE, HOST: For a different perspective now on key foreign policy issues, we turn to Senator Carl Levin, who spent the past week in Iraq, Afghanistan and other countries in the region. Senator, welcome home and welcome back to "FOX News Sunday."

SEN. CARL LEVIN, D-MICH.: Thank you, Chris. Great to be with you.

WALLACE: Thank you. While you were in Iraq, you met with the top political leaders. What's your assessment of the political situation there 3.5 months after the election?

LEVIN: That there's a gridlock and that the Iraqi leaders are going to count on us to protect them, and we should make it very clear to them that we're only going to continue to be there if they work out a political compromise, and that's the message they've not received.

Instead, they get the kind of excuses that we just heard as to how complicated it is, how difficult it is, that constitutions and cabinet selections take time.

They're behind their own schedule for selecting a cabinet, and instead of making it easy for them to continue this gridlock by telling us how complicated it is and by telling the American people to be patient, as the president recently did, we should be putting plenty of pressure on the Iraqis.

WALLACE: But what does that mean? How tough should we get? And specifically what should we do?

LEVIN: We should tell the Iraqis what three of us — a bipartisan letter asked the president to do.

Senator Collins, Jack Reed of Rhode Island and I asked the president to make it clear to the Iraqis that our continued presence in Iraq is dependent upon the Iraqis working out a broad-based political agreement. Otherwise, they're going to continue to get the message, which this administration has given too often, that we're there as long as they need us.

WALLACE: Would you set a specific deadline?

LEVIN: I would not. I would put the word prompt in there, that they must promptly agree to a political settlement. We can't impose it on them. We can't select their leaders. But it's essential that they do it.

But the only way they're going to do it and the only chances that they have of succeeding in defeating the insurgency and ending the violence is if the political leaders come together in a broad-based government.

WALLACE: Let's turn to the military situation. As I say, you were there on the ground this week.

What's your sense of the situation, the danger of civil war and how we're doing in training Iraqi troops to take over for U.S. troops?

LEVIN: I think we're making some progress in terms of training their army, but in terms of training the police to defend the nation, instead of just reflect sectarian points of view and react positively to the militias that they come from, we have not made much progress with the police.

And the police are key. They're the ones that are going to have to prevent civil war from happening inside Baghdad particularly, so the progress has been very, very slow with the police.

WALLACE: This week, Vice President Cheney noted that some top Democrats have objected to the NSA wiretap program, wanted to make changes in the Patriot Act, had called for pullouts, and then he said the following. Let's watch.

(BEGIN VIDEO CLIP)

RICHARD B. CHENEY, VICE PRESIDENT OF THE UNITED STATES: Leading Democrats have demanded a sudden withdrawal from the battle against terrorists in Iraq, the very kind of retreat that Usama bin Laden has been predicting, and with that sorry record, the leaders of the Democratic Party have decided to run on the theme of competence.

(END VIDEO CLIP)

WALLACE: Senator Levin, what do you think of that?

LEVIN: I think that there's been much too much incompetence in this administration and it's a perfectly proper critique of the administration that they've shown incompetence both in the way they've handled the war in Iraq as well as a lot of domestic issues, including Katrina.

So the issue of competence is a very legitimate issue both to raise and to go to elections on.

WALLACE: Before we leave Iraq, as the top Democrat in the Senate Armed Services Committee, what do you make of this Pentagon report that the Russians were passing on U.S. military secrets during the invasion to the Iraqis?

LEVIN: It's possible that it happened. Things like that happen with intelligence by various countries. It would be obviously plenty discouraging as well as disgusting if, in fact, they did it, but sometimes there's disinformation which is provided.

Anything is possible in the area of intelligence. I would not jump to any conclusion one way or the other without a much deeper investigation. But if, in fact, they did it, it, number one, wouldn't surprise me, but it would be very disgusting if they did.

WALLACE: And what would you do to the Russians?

LEVIN: Find ways to let them know that that kind of conduct is not going to be acceptable to us and a whole host of reactions and retaliations.

But I wouldn't prejudge this. The intelligence world is a very murky world, to put it mildly.

WALLACE: Yes, indeed. Let's turn to Afghanistan, another country that you were in this week.

What do you think the prosecution and now the release, apparently, the dismissal, at least, of the case of the Afghan Christian says about the spread of democracy and democratic values in that country?

LEVIN: That there's some hope, that obviously President Karzai was able to find a way to end the prosecution of this man, and that even though the prosecution is very discouraging, that the progress in apparently ending that prosecution of this man is encouraging.

So I have some hope in Afghanistan. Actually, this action reflects, it seems to me, a good reason to be optimistic about Afghanistan. We had the united world going into Afghanistan to go after the Taliban, unlike Iraq, where the world was divided.

We had NATO with us as well as many other countries going into Afghanistan. NATO is taking over now in Afghanistan. So there's really reason to be optimistic in Afghanistan. It's a much better scene than Iraq.

WALLACE: What do you think — on a new subject, what do you think Senator Feingold's mention to censure the president for his NSA warrantless wiretap program?

LEVIN: Well, I think there, first of all, should be, obviously, a hearing as to what happened, the legality of it, the operations of it. I think the president made a mistake in not following the requirements of the law that he seek a warrant.

But in terms of censure, I would not reach any conclusion on that until there have been hearings both on the legality issue as well as how it actually operates, whether or not, in fact, there is probable cause to believe that somebody is engaged in some kind of an operation with the Taliban, as the president says there always is.

But is there, in fact, probable cause before phones are tapped? That is something which should be investigated by both the Intelligence Committee and other appropriate committees.

WALLACE: Well, let me ask you about that. You're a member of this new Intelligence Subcommittee that has been named to oversee the program. Have you been briefed and what have you found out?

LEVIN: My briefing is about halfway through. And I don't want to tell you what I found out.

I'm not allowed to, except I'll tell you what my focus is. My focus is to see whether or not the president of the United States accurately has represented this program as one where there must be probable cause to believe that before an American's phone is tapped that he is either a member of or affiliated with the Taliban or an affiliated organization, or an agent of Taliban or — I mean, sorry, Al Qaeda, excuse me — a member or an agent of Al Qaeda or an affiliated organization.

That is what my focus is going to be, because if that's not true...

WALLACE: And what have you found out so far?

LEVIN: I'm not allowed to tell you what I found out so far because these briefings are highly classified. When I'm finished with my review, which I hope will be in the next few weeks, I hope to find out — I hope to find a way that I can either say yes, the president accurately reflected the program or that I disagree, but I'm not sure I'll be able to even do that within the rules.

WALLACE: Well, let me ask you, just to press this a little bit further, one of your colleagues on this subcommittee, a Democratic colleague, Senator Diane Feinstein, came out afterwards and said that she thought it was a very impressive program and didn't have a contrary word to say about it.

LEVIN: Well, she has, obviously — she feels comfortable saying what she wants to say about her briefing. I don't want to say anything about the way this program operates or reach any conclusion until my briefings are concluded.

But then again, I hope to be able to find a way that I can either look people in the eye and say this program is one where there is probable cause of the precise type that the president assured the nation.

That to me is critical. Then if there is probable cause to believe that these people who are engaged in these conversations are Al Qaeda-connected agents or members, then the question is is it legal, or do you have to modify the law in order to make it legal.

WALLACE: But there's a political reality in this, too, as I don't have to tell you. Do Democrats want to be in the position of investigating the president for possible censure, a president in the middle of wartime, over a program that, at least according to some people who have been briefed on it, including a Democrat, does a good job in protecting the American people?

LEVIN: No, I think it's premature to reach any conclusion about censure, and I would first put the inquiries before you reach any conclusion.

WALLACE: Do you think it was helpful to even raise the idea?

LEVIN: No, I think to say that you should censure the president before you have had the inquiries is premature, so I don't think it's helpful to reach that conclusion at this point.

WALLACE: We're going to have to leave it there, Senator Levin. Thank you. Thanks for coming in after your long trip and, I'm sure, considerable jet lag. Please come back any time, sir.

LEVIN: Thank you.